punycode.go

Documentation: golang.org/x/text/internal/export/idna

     1  // Copyright 2016 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package idna
     6  
     7  // This file implements the Punycode algorithm from RFC 3492.
     8  
     9  import (
    10  	"math"
    11  	"strings"
    12  	"unicode/utf8"
    13  )
    14  
    15  // These parameter values are specified in section 5.
    16  //
    17  // All computation is done with int32s, so that overflow behavior is identical
    18  // regardless of whether int is 32-bit or 64-bit.
    19  const (
    20  	base        int32 = 36
    21  	damp        int32 = 700
    22  	initialBias int32 = 72
    23  	initialN    int32 = 128
    24  	skew        int32 = 38
    25  	tmax        int32 = 26
    26  	tmin        int32 = 1
    27  )
    28  
    29  func punyError(s string) error { return &labelError{s, "A3"} }
    30  
    31  // decode decodes a string as specified in section 6.2.
    32  func decode(encoded string) (string, error) {
    33  	if encoded == "" {
    34  		return "", nil
    35  	}
    36  	pos := 1 + strings.LastIndex(encoded, "-")
    37  	if pos == 1 {
    38  		return "", punyError(encoded)
    39  	}
    40  	if pos == len(encoded) {
    41  		return encoded[:len(encoded)-1], nil
    42  	}
    43  	output := make([]rune, 0, len(encoded))
    44  	if pos != 0 {
    45  		for _, r := range encoded[:pos-1] {
    46  			output = append(output, r)
    47  		}
    48  	}
    49  	i, n, bias := int32(0), initialN, initialBias
    50  	overflow := false
    51  	for pos < len(encoded) {
    52  		oldI, w := i, int32(1)
    53  		for k := base; ; k += base {
    54  			if pos == len(encoded) {
    55  				return "", punyError(encoded)
    56  			}
    57  			digit, ok := decodeDigit(encoded[pos])
    58  			if !ok {
    59  				return "", punyError(encoded)
    60  			}
    61  			pos++
    62  			i, overflow = madd(i, digit, w)
    63  			if overflow {
    64  				return "", punyError(encoded)
    65  			}
    66  			t := k - bias
    67  			if k <= bias {
    68  				t = tmin
    69  			} else if k >= bias+tmax {
    70  				t = tmax
    71  			}
    72  			if digit < t {
    73  				break
    74  			}
    75  			w, overflow = madd(0, w, base-t)
    76  			if overflow {
    77  				return "", punyError(encoded)
    78  			}
    79  		}
    80  		if len(output) >= 1024 {
    81  			return "", punyError(encoded)
    82  		}
    83  		x := int32(len(output) + 1)
    84  		bias = adapt(i-oldI, x, oldI == 0)
    85  		n += i / x
    86  		i %= x
    87  		if n < 0 || n > utf8.MaxRune {
    88  			return "", punyError(encoded)
    89  		}
    90  		output = append(output, 0)
    91  		copy(output[i+1:], output[i:])
    92  		output[i] = n
    93  		i++
    94  	}
    95  	return string(output), nil
    96  }
    97  
    98  // encode encodes a string as specified in section 6.3 and prepends prefix to
    99  // the result.
   100  //
   101  // The "while h < length(input)" line in the specification becomes "for
   102  // remaining != 0" in the Go code, because len(s) in Go is in bytes, not runes.
   103  func encode(prefix, s string) (string, error) {
   104  	output := make([]byte, len(prefix), len(prefix)+1+2*len(s))
   105  	copy(output, prefix)
   106  	delta, n, bias := int32(0), initialN, initialBias
   107  	b, remaining := int32(0), int32(0)
   108  	for _, r := range s {
   109  		if r < 0x80 {
   110  			b++
   111  			output = append(output, byte(r))
   112  		} else {
   113  			remaining++
   114  		}
   115  	}
   116  	h := b
   117  	if b > 0 {
   118  		output = append(output, '-')
   119  	}
   120  	overflow := false
   121  	for remaining != 0 {
   122  		m := int32(0x7fffffff)
   123  		for _, r := range s {
   124  			if m > r && r >= n {
   125  				m = r
   126  			}
   127  		}
   128  		delta, overflow = madd(delta, m-n, h+1)
   129  		if overflow {
   130  			return "", punyError(s)
   131  		}
   132  		n = m
   133  		for _, r := range s {
   134  			if r < n {
   135  				delta++
   136  				if delta < 0 {
   137  					return "", punyError(s)
   138  				}
   139  				continue
   140  			}
   141  			if r > n {
   142  				continue
   143  			}
   144  			q := delta
   145  			for k := base; ; k += base {
   146  				t := k - bias
   147  				if k <= bias {
   148  					t = tmin
   149  				} else if k >= bias+tmax {
   150  					t = tmax
   151  				}
   152  				if q < t {
   153  					break
   154  				}
   155  				output = append(output, encodeDigit(t+(q-t)%(base-t)))
   156  				q = (q - t) / (base - t)
   157  			}
   158  			output = append(output, encodeDigit(q))
   159  			bias = adapt(delta, h+1, h == b)
   160  			delta = 0
   161  			h++
   162  			remaining--
   163  		}
   164  		delta++
   165  		n++
   166  	}
   167  	return string(output), nil
   168  }
   169  
   170  // madd computes a + (b * c), detecting overflow.
   171  func madd(a, b, c int32) (next int32, overflow bool) {
   172  	p := int64(b) * int64(c)
   173  	if p > math.MaxInt32-int64(a) {
   174  		return 0, true
   175  	}
   176  	return a + int32(p), false
   177  }
   178  
   179  func decodeDigit(x byte) (digit int32, ok bool) {
   180  	switch {
   181  	case '0' <= x && x <= '9':
   182  		return int32(x - ('0' - 26)), true
   183  	case 'A' <= x && x <= 'Z':
   184  		return int32(x - 'A'), true
   185  	case 'a' <= x && x <= 'z':
   186  		return int32(x - 'a'), true
   187  	}
   188  	return 0, false
   189  }
   190  
   191  func encodeDigit(digit int32) byte {
   192  	switch {
   193  	case 0 <= digit && digit < 26:
   194  		return byte(digit + 'a')
   195  	case 26 <= digit && digit < 36:
   196  		return byte(digit + ('0' - 26))
   197  	}
   198  	panic("idna: internal error in punycode encoding")
   199  }
   200  
   201  // adapt is the bias adaptation function specified in section 6.1.
   202  func adapt(delta, numPoints int32, firstTime bool) int32 {
   203  	if firstTime {
   204  		delta /= damp
   205  	} else {
   206  		delta /= 2
   207  	}
   208  	delta += delta / numPoints
   209  	k := int32(0)
   210  	for delta > ((base-tmin)*tmax)/2 {
   211  		delta /= base - tmin
   212  		k += base
   213  	}
   214  	return k + (base-tmin+1)*delta/(delta+skew)
   215  }
   216
View as plain text