// Copyright 2019 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 ccitt

import (
	"bytes"
	"fmt"
	"image"
	"image/png"
	"io"
	"io/ioutil"
	"math/rand"
	"os"
	"path/filepath"
	"reflect"
	"strings"
	"testing"
	"unsafe"
)

func compareImages(t *testing.T, img0 image.Image, img1 image.Image) {
	t.Helper()

	b0 := img0.Bounds()
	b1 := img1.Bounds()
	if b0 != b1 {
		t.Fatalf("bounds differ: %v vs %v", b0, b1)
	}

	for y := b0.Min.Y; y < b0.Max.Y; y++ {
		for x := b0.Min.X; x < b0.Max.X; x++ {
			c0 := img0.At(x, y)
			c1 := img1.At(x, y)
			if c0 != c1 {
				t.Fatalf("pixel at (%d, %d) differs: %v vs %v", x, y, c0, c1)
			}
		}
	}
}

func decodePNG(fileName string) (image.Image, error) {
	f, err := os.Open(fileName)
	if err != nil {
		return nil, err
	}
	defer f.Close()
	return png.Decode(f)
}

// simpleHB is a simple implementation of highBits.
func simpleHB(dst []byte, src []byte, invert bool) (d int, s int) {
	for d < len(dst) {
		numToPack := len(src) - s
		if numToPack <= 0 {
			break
		} else if numToPack > 8 {
			numToPack = 8
		}

		byteValue := byte(0)
		if invert {
			byteValue = 0xFF >> uint(numToPack)
		}
		for n := 0; n < numToPack; n++ {
			byteValue |= (src[s] & 0x80) >> uint(n)
			s++
		}
		dst[d] = byteValue
		d++
	}
	return d, s
}

func TestHighBits(t *testing.T) {
	rng := rand.New(rand.NewSource(1))
	dst0 := make([]byte, 3)
	dst1 := make([]byte, 3)
	src := make([]byte, 20)

	for r := 0; r < 1000; r++ {
		numDst := rng.Intn(len(dst0) + 1)
		randomByte := byte(rng.Intn(256))
		for i := 0; i < numDst; i++ {
			dst0[i] = randomByte
			dst1[i] = randomByte
		}

		numSrc := rng.Intn(len(src) + 1)
		for i := 0; i < numSrc; i++ {
			src[i] = byte(rng.Intn(256))
		}

		invert := rng.Intn(2) == 0

		d0, s0 := highBits(dst0[:numDst], src[:numSrc], invert)
		d1, s1 := simpleHB(dst1[:numDst], src[:numSrc], invert)

		if (d0 != d1) || (s0 != s1) || !bytes.Equal(dst0[:numDst], dst1[:numDst]) {
			srcHighBits := make([]byte, numSrc)
			for i := range srcHighBits {
				srcHighBits[i] = src[i] >> 7
			}

			t.Fatalf("r=%d, numDst=%d, numSrc=%d, invert=%t:\nsrcHighBits=%d\n"+
				"got  d=%d, s=%d, bytes=[% 02X]\n"+
				"want d=%d, s=%d, bytes=[% 02X]",
				r, numDst, numSrc, invert, srcHighBits,
				d0, s0, dst0[:numDst],
				d1, s1, dst1[:numDst],
			)
		}
	}
}

func BenchmarkHighBits(b *testing.B) {
	rng := rand.New(rand.NewSource(1))
	dst := make([]byte, 1024)
	src := make([]byte, 7777)
	for i := range src {
		src[i] = uint8(rng.Intn(256))
	}

	b.ResetTimer()
	for n := 0; n < b.N; n++ {
		highBits(dst, src, false)
		highBits(dst, src, true)
	}
}

func TestMaxCodeLength(t *testing.T) {
	br := bitReader{}
	size := unsafe.Sizeof(br.bits)
	size *= 8 // Convert from bytes to bits.

	// Check that the size of the bitReader.bits field is large enough to hold
	// nextBitMaxNBits bits.
	if size < nextBitMaxNBits {
		t.Fatalf("size: got %d, want >= %d", size, nextBitMaxNBits)
	}

	// Check that bitReader.nextBit will always leave enough spare bits in the
	// bitReader.bits field such that the decode function can unread up to
	// maxCodeLength bits.
	if want := size - nextBitMaxNBits; maxCodeLength > want {
		t.Fatalf("maxCodeLength: got %d, want <= %d", maxCodeLength, want)
	}

	// The decode function also assumes that, when saving bits to possibly
	// unread later, those bits fit inside a uint32.
	if maxCodeLength > 32 {
		t.Fatalf("maxCodeLength: got %d, want <= %d", maxCodeLength, 32)
	}
}

func testDecodeTable(t *testing.T, decodeTable [][2]int16, codes []code, values []uint32) {
	// Build a map from values to codes.
	m := map[uint32]string{}
	for _, code := range codes {
		m[code.val] = code.str
	}

	// Build the encoded form of those values in MSB order.
	enc := []byte(nil)
	bits := uint8(0)
	nBits := uint32(0)
	for _, v := range values {
		code := m[v]
		if code == "" {
			panic("unmapped code")
		}
		for _, c := range code {
			bits |= uint8(c&1) << (7 - nBits)
			nBits++
			if nBits == 8 {
				enc = append(enc, bits)
				bits = 0
				nBits = 0
				continue
			}
		}
	}
	if nBits > 0 {
		enc = append(enc, bits)
	}

	// Decode that encoded form.
	got := []uint32(nil)
	r := &bitReader{
		r:     bytes.NewReader(enc),
		order: MSB,
	}
	finalValue := values[len(values)-1]
	for {
		v, err := decode(r, decodeTable)
		if err != nil {
			t.Fatalf("after got=%d: %v", got, err)
		}
		got = append(got, v)
		if v == finalValue {
			break
		}
	}

	// Check that the round-tripped values were unchanged.
	if !reflect.DeepEqual(got, values) {
		t.Fatalf("\ngot:  %v\nwant: %v", got, values)
	}
}

func TestModeDecodeTable(t *testing.T) {
	testDecodeTable(t, modeDecodeTable[:], modeCodes, []uint32{
		modePass,
		modeV0,
		modeV0,
		modeVL1,
		modeVR3,
		modeVL2,
		modeExt,
		modeVL1,
		modeH,
		modeVL1,
		modeVL1,
		// The exact value of this final slice element doesn't really matter,
		// except that testDecodeTable assumes that it (the finalValue) is
		// different from every previous element.
		modeVL3,
	})
}

func TestWhiteDecodeTable(t *testing.T) {
	testDecodeTable(t, whiteDecodeTable[:], whiteCodes, []uint32{
		0, 1, 256, 7, 128, 3, 2560,
	})
}

func TestBlackDecodeTable(t *testing.T) {
	testDecodeTable(t, blackDecodeTable[:], blackCodes, []uint32{
		63, 64, 63, 64, 64, 63, 22, 1088, 2048, 7, 6, 5, 4, 3, 2, 1, 0,
	})
}

func TestDecodeInvalidCode(t *testing.T) {
	// The bit stream is:
	// 1 010 000000011011
	// Packing that LSB-first gives:
	// 0b_1101_1000_0000_0101
	src := []byte{0x05, 0xD8}

	decodeTable := modeDecodeTable[:]
	r := &bitReader{
		r: bytes.NewReader(src),
	}

	// "1" decodes to the value 2.
	if v, err := decode(r, decodeTable); v != 2 || err != nil {
		t.Fatalf("decode #0: got (%v, %v), want (2, nil)", v, err)
	}

	// "010" decodes to the value 6.
	if v, err := decode(r, decodeTable); v != 6 || err != nil {
		t.Fatalf("decode #0: got (%v, %v), want (6, nil)", v, err)
	}

	// "00000001" is an invalid code.
	if v, err := decode(r, decodeTable); v != 0 || err != errInvalidCode {
		t.Fatalf("decode #0: got (%v, %v), want (0, %v)", v, err, errInvalidCode)
	}

	// The bitReader should not have advanced after encountering an invalid
	// code. The remaining bits should be "000000011011".
	remaining := []byte(nil)
	for {
		bit, err := r.nextBit()
		if err == io.EOF {
			break
		} else if err != nil {
			t.Fatalf("nextBit: %v", err)
		}
		remaining = append(remaining, uint8('0'+bit))
	}
	if got, want := string(remaining), "000000011011"; got != want {
		t.Fatalf("remaining bits: got %q, want %q", got, want)
	}
}

func testRead(t *testing.T, fileName string, sf SubFormat, align, invert, truncated bool) {
	t.Helper()

	const width, height = 153, 55
	opts := &Options{
		Align:  align,
		Invert: invert,
	}

	got := ""
	{
		f, err := os.Open(fileName)
		if err != nil {
			t.Fatalf("Open: %v", err)
		}
		defer f.Close()
		gotBytes, err := ioutil.ReadAll(NewReader(f, MSB, sf, width, height, opts))
		if err != nil {
			t.Fatalf("ReadAll: %v", err)
		}
		got = string(gotBytes)
	}

	want := ""
	{
		img, err := decodePNG("testdata/bw-gopher.png")
		if err != nil {
			t.Fatalf("decodePNG: %v", err)
		}
		gray, ok := img.(*image.Gray)
		if !ok {
			t.Fatalf("decodePNG: got %T, want *image.Gray", img)
		}
		bounds := gray.Bounds()
		if w := bounds.Dx(); w != width {
			t.Fatalf("width: got %d, want %d", w, width)
		}
		if h := bounds.Dy(); h != height {
			t.Fatalf("height: got %d, want %d", h, height)
		}

		// Prepare to extend each row's width to a multiple of 8, to simplify
		// packing from 1 byte per pixel to 1 bit per pixel.
		extended := make([]byte, (width+7)&^7)

		wantBytes := []byte(nil)
		for y := bounds.Min.Y; y < bounds.Max.Y; y++ {
			rowPix := gray.Pix[(y-bounds.Min.Y)*gray.Stride:]
			rowPix = rowPix[:width]
			copy(extended, rowPix)

			// Pack from 1 byte per pixel to 1 bit per pixel, MSB first.
			byteValue := uint8(0)
			for x, pixel := range extended {
				byteValue |= (pixel & 0x80) >> uint(x&7)
				if (x & 7) == 7 {
					wantBytes = append(wantBytes, byteValue)
					byteValue = 0
				}
			}
		}
		want = string(wantBytes)
	}

	// We expect a width of 153 pixels, which is 20 bytes per row (at 1 bit per
	// pixel, plus 7 final bits of padding). Check that want is 20 * height
	// bytes long, and if got != want, format them to split at every 20 bytes.

	if n := len(want); n != 20*height {
		t.Fatalf("len(want): got %d, want %d", n, 20*height)
	}

	format := func(s string) string {
		b := []byte(nil)
		for row := 0; len(s) >= 20; row++ {
			b = append(b, fmt.Sprintf("row%02d: %02X\n", row, s[:20])...)
			s = s[20:]
		}
		if len(s) > 0 {
			b = append(b, fmt.Sprintf("%02X\n", s)...)
		}
		return string(b)
	}

	if got != want {
		t.Fatalf("got:\n%s\nwant:\n%s", format(got), format(want))
	}

	// Passing AutoDetectHeight should produce the same output, provided that
	// the input hasn't truncated the trailing sequence of consecutive EOL's
	// that marks the end of the image.
	if !truncated {
		f, err := os.Open(fileName)
		if err != nil {
			t.Fatalf("Open: %v", err)
		}
		defer f.Close()
		adhBytes, err := ioutil.ReadAll(NewReader(f, MSB, sf, width, AutoDetectHeight, opts))
		if err != nil {
			t.Fatalf("ReadAll: %v", err)
		}
		if s := string(adhBytes); s != want {
			t.Fatalf("AutoDetectHeight produced different output.\n"+
				"height=%d:\n%s\nheight=%d:\n%s",
				AutoDetectHeight, format(s), height, format(want))
		}
	}
}

func TestRead(t *testing.T) {
	for _, fileName := range []string{
		"testdata/bw-gopher.ccitt_group3",
		"testdata/bw-gopher-aligned.ccitt_group3",
		"testdata/bw-gopher-inverted.ccitt_group3",
		"testdata/bw-gopher-inverted-aligned.ccitt_group3",
		"testdata/bw-gopher.ccitt_group4",
		"testdata/bw-gopher-aligned.ccitt_group4",
		"testdata/bw-gopher-inverted.ccitt_group4",
		"testdata/bw-gopher-inverted-aligned.ccitt_group4",
		"testdata/bw-gopher-truncated0.ccitt_group3",
		"testdata/bw-gopher-truncated0.ccitt_group4",
		"testdata/bw-gopher-truncated1.ccitt_group3",
		"testdata/bw-gopher-truncated1.ccitt_group4",
	} {
		subFormat := Group3
		if strings.HasSuffix(fileName, "group4") {
			subFormat = Group4
		}
		align := strings.Contains(fileName, "aligned")
		invert := strings.Contains(fileName, "inverted")
		truncated := strings.Contains(fileName, "truncated")
		testRead(t, fileName, subFormat, align, invert, truncated)
	}
}

func TestDecodeIntoGray(t *testing.T) {
	for _, tt := range []struct {
		fileName string
		sf       SubFormat
		w, h     int
	}{
		{"testdata/bw-gopher.ccitt_group3", Group3, 153, 55},
		{"testdata/bw-gopher.ccitt_group4", Group4, 153, 55},
		{"testdata/bw-gopher-truncated0.ccitt_group3", Group3, 153, 55},
		{"testdata/bw-gopher-truncated0.ccitt_group4", Group4, 153, 55},
		{"testdata/bw-gopher-truncated1.ccitt_group3", Group3, 153, 55},
		{"testdata/bw-gopher-truncated1.ccitt_group4", Group4, 153, 55},
	} {
		t.Run(tt.fileName, func(t *testing.T) {
			testDecodeIntoGray(t, tt.fileName, MSB, tt.sf, tt.w, tt.h, nil)
		})
	}
}

func testDecodeIntoGray(t *testing.T, fileName string, order Order, sf SubFormat, width int, height int, opts *Options) {
	t.Helper()

	f, err := os.Open(filepath.FromSlash(fileName))
	if err != nil {
		t.Fatalf("Open: %v", err)
	}
	defer f.Close()

	got := image.NewGray(image.Rect(0, 0, width, height))
	if err := DecodeIntoGray(got, f, order, sf, opts); err != nil {
		t.Fatalf("DecodeIntoGray: %v", err)
	}

	want, err := decodePNG("testdata/bw-gopher.png")
	if err != nil {
		t.Fatal(err)
	}

	compareImages(t, got, want)
}