// Copyright 2016 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package idna

// This file implements the Punycode algorithm from RFC 3492.

import (
	"math"
	"strings"
	"unicode/utf8"
)

// These parameter values are specified in section 5.
//
// All computation is done with int32s, so that overflow behavior is identical
// regardless of whether int is 32-bit or 64-bit.
const (
	base        int32 = 36
	damp        int32 = 700
	initialBias int32 = 72
	initialN    int32 = 128
	skew        int32 = 38
	tmax        int32 = 26
	tmin        int32 = 1
)

// maxPunycodeLen is the maximum number of runes allowed in a Punycode-encoded
// or decoded label, preventing quadratic behavior on large inputs.
const maxPunycodeLen = 256

func punyError(s string) error { return &labelError{s, "P4"} }

// decode decodes a string as specified in section 6.2.
func decode(encoded string) (string, error) {
	if encoded == "" {
		return "", nil
	}
	pos := 1 + strings.LastIndex(encoded, "-")
	if pos == 1 {
		return "", punyError(encoded)
	}
	if pos == len(encoded) {
		if utf8.RuneCountInString(encoded[:len(encoded)-1]) > maxPunycodeLen {
			return "", punyError(encoded)
		}
		return encoded[:len(encoded)-1], nil
	}
	// [64]rune is enough to hold any DNS-valid label, and will live on the stack.
	// Longer, invalid labels may move the buffer to the heap on append.
	var outputBuf [64]rune
	output := outputBuf[:0]
	if pos != 0 {
		for _, r := range encoded[:pos-1] {
			if len(output) >= maxPunycodeLen {
				return "", punyError(encoded)
			}
			output = append(output, r)
		}
	}
	i, n, bias := int32(0), initialN, initialBias
	overflow := false
	for pos < len(encoded) {
		oldI, w := i, int32(1)
		for k := base; ; k += base {
			if pos == len(encoded) {
				return "", punyError(encoded)
			}
			digit, ok := decodeDigit(encoded[pos])
			if !ok {
				return "", punyError(encoded)
			}
			pos++
			i, overflow = madd(i, digit, w)
			if overflow {
				return "", punyError(encoded)
			}
			t := k - bias
			if k <= bias {
				t = tmin
			} else if k >= bias+tmax {
				t = tmax
			}
			if digit < t {
				break
			}
			w, overflow = madd(0, w, base-t)
			if overflow {
				return "", punyError(encoded)
			}
		}
		if len(output) >= maxPunycodeLen {
			return "", punyError(encoded)
		}
		x := int32(len(output) + 1)
		bias = adapt(i-oldI, x, oldI == 0)
		n += i / x
		i %= x
		if n < 0 || n > utf8.MaxRune {
			return "", punyError(encoded)
		}
		output = append(output, 0)
		copy(output[i+1:], output[i:])
		output[i] = n
		i++
	}
	return string(output), nil
}

// encode encodes a string as specified in section 6.3 and prepends prefix to
// the result.
//
// The "while h < length(input)" line in the specification becomes "for
// remaining != 0" in the Go code, because len(s) in Go is in bytes, not runes.
func encode(prefix, s string) (string, error) {
	output := make([]byte, len(prefix), min(len(prefix)+1+2*len(s), maxPunycodeLen))
	copy(output, prefix)
	delta, n, bias := int32(0), initialN, initialBias
	b, remaining := int32(0), int32(0)
	// [64]rune is enough to hold any DNS-valid label, and will live on the stack.
	// Longer, invalid labels may move the buffer to the heap on append.
	var inputBuf [64]rune
	input := inputBuf[:0]
	for _, r := range s {
		if unicode16 && r == 0xfffd {
			return s, &labelError{s, "A3"}
		}
		if len(input) >= maxPunycodeLen {
			return "", punyError(s)
		}
		input = append(input, r)
		if r < 0x80 {
			b++
			output = append(output, byte(r))
		} else {
			remaining++
		}
	}
	h := b
	if b > 0 {
		output = append(output, '-')
	}
	overflow := false
	for remaining != 0 {
		m := int32(0x7fffffff)
		for _, r := range input {
			if m > r && r >= n {
				m = r
			}
		}
		delta, overflow = madd(delta, m-n, h+1)
		if overflow {
			return "", punyError(s)
		}
		n = m
		for _, r := range input {
			if r < n {
				delta++
				if delta < 0 {
					return "", punyError(s)
				}
				continue
			}
			if r > n {
				continue
			}
			q := delta
			for k := base; ; k += base {
				t := k - bias
				if k <= bias {
					t = tmin
				} else if k >= bias+tmax {
					t = tmax
				}
				if q < t {
					break
				}
				output = append(output, encodeDigit(t+(q-t)%(base-t)))
				q = (q - t) / (base - t)
			}
			output = append(output, encodeDigit(q))
			bias = adapt(delta, h+1, h == b)
			delta = 0
			h++
			remaining--
		}
		delta++
		n++
	}
	return string(output), nil
}

// madd computes a + (b * c), detecting overflow.
func madd(a, b, c int32) (next int32, overflow bool) {
	p := int64(b) * int64(c)
	if p > math.MaxInt32-int64(a) {
		return 0, true
	}
	return a + int32(p), false
}

func decodeDigit(x byte) (digit int32, ok bool) {
	switch {
	case '0' <= x && x <= '9':
		return int32(x - ('0' - 26)), true
	case 'A' <= x && x <= 'Z':
		return int32(x - 'A'), true
	case 'a' <= x && x <= 'z':
		return int32(x - 'a'), true
	}
	return 0, false
}

func encodeDigit(digit int32) byte {
	switch {
	case 0 <= digit && digit < 26:
		return byte(digit + 'a')
	case 26 <= digit && digit < 36:
		return byte(digit + ('0' - 26))
	}
	panic("idna: internal error in punycode encoding")
}

// adapt is the bias adaptation function specified in section 6.1.
func adapt(delta, numPoints int32, firstTime bool) int32 {
	if firstTime {
		delta /= damp
	} else {
		delta /= 2
	}
	delta += delta / numPoints
	k := int32(0)
	for delta > ((base-tmin)*tmax)/2 {
		delta /= base - tmin
		k += base
	}
	return k + (base-tmin+1)*delta/(delta+skew)
}