func (s *XLSuite) TestInsert(c *C) {

	var (
		hc, bitmap      uint32
		lev             uint32
		idx             uint32
		flag, mask, pos uint32
		where           uint32
	)
	rng := xr.MakeSimpleRNG()
	perm := rng.Perm(32) // a random permutation of [0..32)
	var slice []byte

	for i := byte(0); i < 32; i++ {
		hc = uint32(perm[i])
		// insert the value into the hash slice in such a way as
		// to maintain order
		idx = (hc >> lev) & 0x1f
		c.Assert(idx, Equals, hc) // hc is restricted to that range
		where = s.insertHash(c, &slice, byte(idx))
		flag = uint32(1) << (idx + 1)
		mask = flag - 1
		//pos = intgr.BitCount(int(bitmap) & mask)
		pos = uint32(xu.BitCount32(bitmap & mask))
		occupied := uint32(1 << idx)
		bitmap |= occupied

		//fmt.Printf("%02d: hc %02x, idx %02x, mask 0x%08x, bitmap 0x%08x, pos %02d where %02d\n\n",
		//	i, hc, idx, mask, bitmap, pos, where)
		c.Assert(pos, Equals, where)
	}

}

// Verify that 0.0.0.0 is acceptable as an address (meaning "listen
// on all interfaces")
//
func (s *XLSuite) TestAllInterfaces(c *C) {
	rng := xr.MakeSimpleRNG()
	var str string

	// test with port = 0 (meaning the system decides)
	str = "0.0.0.0:0"
	a, err := NewV4Address(str)
	c.Assert(err, IsNil)
	c.Assert(a.String(), Equals, str)

	// test with random port
	port := rng.Intn(256 * 256)
	str = fmt.Sprintf("0.0.0.0:%d", port)
	a, err = NewV4Address(str)
	c.Assert(err, IsNil)
	c.Assert(a.String(), Equals, str)

	// ABBREVIATED as [::]; test with port = 0
	str = "[::]:0"
	a, err = NewV4Address(str)
	c.Assert(err, IsNil)
	c.Assert(a.String(), Equals, "0.0.0.0:0")

	// test with random port
	port = rng.Intn(256 * 256)
	str = fmt.Sprintf("0.0.0.0:%d", port)
	a, err = NewV4Address(str)
	c.Assert(err, IsNil)
	c.Assert(a.String(), Equals, str)
}

func (s *XLSuite) TestMakingPermutedKeys(c *C) {

	rng := xr.MakeSimpleRNG()
	var w uint
	for w = uint(4); w < uint(7); w++ {
		fields, keys := s.makePermutedKeys(rng, w)
		flag := uint64(1 << w)
		mask := flag - 1
		maxDepth := 64 / w // rounding down
		fieldCount := uint(len(fields))
		// we are relying on Hashcode(), which has only 64 bits
		if maxDepth > fieldCount {
			maxDepth = fieldCount
		}
		for i := uint(0); i < maxDepth; i++ {
			bKey, err := NewBytesKey(keys[i])
			c.Assert(err, IsNil)
			hc := bKey.Hashcode()
			for j := uint(0); j <= i; j++ {
				ndx := hc & mask
				if uint(ndx) != uint(fields[j]) {
					fmt.Printf(
						"GLITCH: w %d keyset %d field[%2d] %02x ndx %02x\n",
						w, i, j, fields[j], ndx)
				}
				c.Assert(uint(ndx), Equals, uint(fields[j]))
				hc >>= w
			}
		}
	}
}

func (s *XLSuite) TestKeySelector64(c *C) {

	rng := xr.MakeSimpleRNG()
	// m := uint(10 + rng.Intn(15))	// so 10..24
	s.doTestKeySelector64(c, rng, true, 24)
	s.doTestKeySelector64(c, rng, false, 24)
}

func makeSomeUniqueKeys(N, K uint) (rawKeys [][]byte, bKeys []gh.BytesKey) {

	rng := xr.MakeSimpleRNG()
	rawKeys = make([][]byte, N)
	bKeys = make([]gh.BytesKey, N)
	keyMap := make(map[uint64]bool)

	for i := uint(0); i < N; i++ {
		var bKey gh.BytesKey
		key := make([]byte, K)
		for {
			rng.NextBytes(key)
			bKey, _ = gh.NewBytesKey(key)
			hc := bKey.Hashcode()
			_, ok := keyMap[hc]
			if !ok { // value is not in the map
				keyMap[hc] = true
				break
			}
		}
		rawKeys[i] = key
		bKeys[i] = bKey
	}
	return
}

func (s *XLSuite) TestPow2_64(c *C) {
	if VERBOSITY > 0 {
		fmt.Println("TEST_POW2_64")
	}
	rng := xr.MakeSimpleRNG()
	_ = rng

	c.Assert(NextPow2_64(0), Equals, uint64(1))
	c.Assert(NextPow2_64(1), Equals, uint64(1))
	c.Assert(NextPow2_64(2), Equals, uint64(2))
	c.Assert(NextPow2_64(7), Equals, uint64(8))
	c.Assert(NextPow2_64(8), Equals, uint64(8))
	c.Assert(NextPow2_64(9), Equals, uint64(16))
	c.Assert(NextPow2_64(1023), Equals, uint64(1024))
	c.Assert(NextPow2_64(1024), Equals, uint64(1024))
	c.Assert(NextPow2_64(1025), Equals, uint64(2048))

	// Test all powers of 2
	n := uint64(4)
	for i := 2; i < 64; i++ {
		c.Assert(NextPow2_64(n), Equals, n)
		n <<= 1
	}

	// Test random values
	n = uint64(4)
	for i := 2; i < 63; i++ {
		lowBits := uint64(rng.Int63n(int64(n)))
		if lowBits != uint64(0) {
			c.Assert(NextPow2_64(n+lowBits), Equals, 2*n)
		}
		n <<= 1
	}
}

func (s *XLSuite) TestHamtTopBottomIDMap(c *C) {
	if VERBOSITY > 0 {
		fmt.Println("TEST_HAMT_TOP_BOTTOM_MAP")
	}
	var err error

	m, err := NewNewIDMapHAMT()
	c.Assert(err, IsNil)

	rng := xr.MakeSimpleRNG()
	topBNI, bottomBNI := s.makeTopAndBottomBNI(c, rng)
	bottomKey := bottomBNI.GetNodeID().Value()
	topKey := topBNI.GetNodeID().Value()

	err = m.Insert(topKey, topBNI)
	c.Assert(err, IsNil)
	err = m.Insert(bottomKey, bottomBNI)
	c.Assert(err, IsNil)
	entryCount, _, _ := m.Size()
	c.Assert(entryCount, Equals, uint(2))

	// insert a duplicate
	err = m.Insert(bottomKey, bottomBNI)
	c.Assert(err, IsNil)
	entryCount, _, _ = m.Size()
	c.Assert(entryCount, Equals, uint(2))

}

func (s *XLSuite) TestSNode(c *C) {
	var err error
	rng := xr.MakeSimpleRNG()

	const COUNT = uint(8)
	keys := make([]BytesKey, COUNT)
	values := make([]interface{}, COUNT)
	hashCodes := make([]uint, COUNT)

	for i := uint(0); i < COUNT; i++ {
		length := 8 + rng.Intn(32) // so [8,40) bytes
		data := make([]byte, length)
		rng.NextBytes(data)
		key := NewBytesKey(data)
		var shc uint32
		var hc uint
		shc, err = key.Hashcode()
		hc = uint(shc)
		c.Assert(err, IsNil)
		keys[i] = *key
		hashCodes[i] = hc
		dummyVal := &DummyValue{i}
		values[i] = dummyVal
	}

	// a trivial test, presumably will be elaborated over time
	for i := uint(0); i < COUNT; i++ {
		var hc uint32
		hc, err = keys[i].Hashcode()
		c.Assert(uint(hc), Equals, hashCodes[i])
		expectedV := &DummyValue{n: i}
		c.Assert(values[i], DeepEquals, expectedV)
	}
}

// Create a new 16x16 file system, ORing perm into the default permissions.
// If perm is 0, the default is to allow user and group access.
// If the root is U, then this creates U/, U/tmp, U/in, and the top-level
// hex directories U/x
func NewU16x16(path string, perm os.FileMode) (udir *U16x16, err error) {
	// TODO: validate path
	var (
		inDir, tmpDir string
	)
	err = os.MkdirAll(path, 0750|perm)
	if err == nil {
		inDir = filepath.Join(path, "in")
		err = os.MkdirAll(inDir, 0770|perm)
		if err == nil {
			tmpDir = filepath.Join(path, "tmp")
			err = os.MkdirAll(tmpDir, 0700)
			if err == nil {
				for i := 0; i < 16; i++ {
					hexDir := fmt.Sprintf("%x", i)
					hexPath := filepath.Join(path, hexDir)
					err = os.MkdirAll(hexPath, 0750|perm)
					if err != nil {
						break
					}
				}
			}
		}
	}
	udir = &U16x16{
		path:   path,
		rng:    xr.MakeSimpleRNG(),
		inDir:  inDir,
		tmpDir: tmpDir,
	}
	return
}

//// DEBUG
//func dumpBuffer( title string, p*[]byte) {
//    length := len(*p)
//    fmt.Printf("%s ", title)
//    for i := 0; i < length; i++ {
//        fmt.Printf("%02x ", (*p)[i])
//    }
//    fmt.Print("\n")
//}
//// END
func (s *XLSuite) TestReadWrite(c *C) {
	const COUNT = 16
	const MAX_TYPE = 128
	rng := xr.MakeSimpleRNG()
	for i := 0; i < COUNT; i++ {
		tType := uint16(rng.NextInt32(MAX_TYPE))
		bufLen := 4 * (1 + int(rng.NextInt32(16)))
		value := make([]byte, bufLen)
		rng.NextBytes(value) // just adds noise
		tlv := new(TLV16)
		tlv.Init(tType, &value)

		// create a buffer, write TLV16 into it, read it back
		buffer := make([]byte, 4+bufLen)
		// XXX offset should be randomized
		offset := uint16(0)
		tlv.Encode(&buffer, offset)
		decoded := Decode(&buffer, offset)
		c.Assert(tType, Equals, decoded.Type())
		c.Assert(bufLen, Equals, int(decoded.Length()))
		//      // DEBUG
		//      dumpBuffer("value   ", &buffer)
		//      dumpBuffer("encoded ", decoded.Value())
		//      // END
		for j := 0; j < bufLen; j++ {
			c.Assert((*tlv.Value())[j], Equals, (*decoded.Value())[j])
		}
	}
}

func (s *XLSuite) TestParser(c *C) {
	// fmt.Println("TEST_PARSER")
	rng := xr.MakeSimpleRNG()
	for i := 0; i < 16; i++ {
		s.doTestParser(c, rng)
	}
}

func (s *XLSuite) TestLeaf(c *C) {
	const MIN_KEY_LEN = 8
	rng := xr.MakeSimpleRNG()
	_ = rng

	// a nil argument must cause an error
	p := 0
	gk := make([]byte, MIN_KEY_LEN)
	goodKey, err := NewBytesKey(gk)
	c.Assert(err, IsNil)

	sk := make([]byte, MIN_KEY_LEN-1)
	_, err = NewBytesKey(sk)
	// must fail - key is too short
	c.Assert(err, NotNil)

	_, err = NewLeaf(nil, &p)
	c.Assert(err, NotNil)

	_, err = NewLeaf(goodKey, nil)
	c.Assert(err, NotNil)

	leaf, err := NewLeaf(goodKey, &p)
	c.Assert(err, IsNil)
	c.Assert(leaf, NotNil)
	c.Assert(leaf.IsLeaf(), Equals, true)

	// XXX test a Table, IsLeaf() should return false
	// XXX STUB

}

func (s *XLSuite) TestByteBuffer(c *C) {
	if VERBOSITY > 0 {
		fmt.Println("TEST_BYTE_BUFFER")
	}

	var soFar, totalSize int

	rng := xr.MakeSimpleRNG()
	count := 8 + rng.Intn(8)
	p := make([][]byte, count)  // we make this many little slices
	sizes := make([]int, count) // the length of each
	for i := 0; i < count; i++ {
		size := 16 + rng.Intn(16)
		sizes[i] = size
		p[i] = make([]byte, size)
		rng.NextBytes(p[i]) // fill the slice with random values
		totalSize = totalSize + size
	}
	capacity := 2 * totalSize
	b, err := NewByteBuffer(capacity)
	c.Assert(err, IsNil)
	c.Assert(b.Len(), Equals, 0)
	c.Assert(b.Cap(), Equals, capacity)

	for i := 0; i < count; i++ {
		n, err := b.Write(p[i])
		c.Assert(err, IsNil)
		c.Assert(n, Equals, sizes[i])
		soFar += n
		c.Assert(b.Len(), Equals, soFar)
	}
}

func (s *XLSuite) TestBadLengths(c *C) {

	datum, err := xi.New(nil) // generates random NodeID

	rng := xr.MakeSimpleRNG()
	ndx := uint32(rng.Intn(256 * 256 * 256))
	okData := make([]byte, 256+rng.Intn(3))

	// verify nil datum causes error
	nilChunk, err := NewChunk(nil, ndx, okData)
	c.Assert(err, Equals, NilDatum)
	c.Assert(nilChunk, Equals, (*Chunk)(nil))

	// verify nil data causes error
	nilChunk, err = NewChunk(datum, ndx, nil)
	c.Assert(err, Equals, NilData)
	c.Assert(nilChunk, Equals, (*Chunk)(nil))

	// verify length of zero causes error
	zeroLenData := make([]byte, 0)
	lenZeroChunk, err := NewChunk(datum, ndx, zeroLenData)
	c.Assert(err, Equals, ZeroLengthChunk)
	c.Assert(lenZeroChunk, Equals, (*Chunk)(nil))

	// verify length > MAX_CHUNK_BYTES causes error
	bigData := make([]byte, MAX_CHUNK_BYTES+1+rng.Intn(3))
	tooBig, err := NewChunk(datum, ndx, bigData)
	c.Assert(err, Equals, ChunkTooLong)
	c.Assert(tooBig, Equals, (*Chunk)(nil))
}

func (s *XLSuite) TestHamtFindID(c *C) {
	if VERBOSITY > 0 {
		fmt.Println("TEST_HAMT_FIND_ID")
	}
	var err error

	m, err := NewNewIDMapHAMT()
	c.Assert(err, IsNil)

	rng := xr.MakeSimpleRNG()
	baseNode0123 := s.makeABNI(c, rng, "baseNode0123", 0, 1, 2, 3)
	baseNode1 := s.makeABNI(c, rng, "baseNode1", 1)
	baseNode12 := s.makeABNI(c, rng, "baseNode12", 1, 2)
	baseNode123 := s.makeABNI(c, rng, "baseNode123", 1, 2, 3)
	baseNode4 := s.makeABNI(c, rng, "baseNode4", 4)
	baseNode42 := s.makeABNI(c, rng, "baseNode42", 4, 2)
	baseNode423 := s.makeABNI(c, rng, "baseNode423", 4, 2, 3)
	baseNode5 := s.makeABNI(c, rng, "baseNode5", 5)
	baseNode6 := s.makeABNI(c, rng, "baseNode6", 6)
	baseNode62 := s.makeABNI(c, rng, "baseNode62", 6, 2)
	baseNode623 := s.makeABNI(c, rng, "baseNode623", 6, 2, 3)

	// TODO: randomize order in which baseNodes are added
	s.addIDToHAMT(c, m, baseNode123)
	s.addIDToHAMT(c, m, baseNode12)
	s.addIDToHAMT(c, m, baseNode1)

	s.addIDToHAMT(c, m, baseNode5)

	s.addIDToHAMT(c, m, baseNode4)
	s.addIDToHAMT(c, m, baseNode42)
	s.addIDToHAMT(c, m, baseNode423)

	s.addIDToHAMT(c, m, baseNode6)
	s.addIDToHAMT(c, m, baseNode623)
	s.addIDToHAMT(c, m, baseNode62)

	s.addIDToHAMT(c, m, baseNode0123)

	// adding duplicates should have no effect
	s.addIDToHAMT(c, m, baseNode4)
	s.addIDToHAMT(c, m, baseNode42)
	s.addIDToHAMT(c, m, baseNode423)

	// TODO: randomize order in which finding baseNodes is tested
	s.findIDInHAMT(c, m, baseNode0123)

	s.findIDInHAMT(c, m, baseNode1)
	s.findIDInHAMT(c, m, baseNode12)
	s.findIDInHAMT(c, m, baseNode123)

	s.findIDInHAMT(c, m, baseNode4)
	s.findIDInHAMT(c, m, baseNode42)
	s.findIDInHAMT(c, m, baseNode423)

	s.findIDInHAMT(c, m, baseNode6)
	s.findIDInHAMT(c, m, baseNode62)
	s.findIDInHAMT(c, m, baseNode623)
}

func (s *XLSuite) TestRegexes(c *C) {
	rng := xr.MakeSimpleRNG()
	for i := 0; i < 8; i++ {
		s.doTestRegexes(c, rng, xu.USING_SHA1)
		s.doTestRegexes(c, rng, xu.USING_SHA2)
		s.doTestRegexes(c, rng, xu.USING_SHA3)
	}
}

func (s *XLSuite) TestHamtEntrySplittingInserts(c *C) {
	if VERBOSITY > 0 {
		fmt.Println("TEST_HAMT_ENTRY_SPLITTING_INSERTS")
	}
	rng := xr.MakeSimpleRNG()

	s.doTestHamtEntrySplittingInserts(c, rng, 5, 5)
}

func (s *XLSuite) TestSameNodeID(c *C) {
	rng := xr.MakeSimpleRNG()
	id1 := s.makeANodeID(c, rng)
	c.Assert(SameNodeID(id1, id1), Equals, true)

	id2 := s.makeANodeID(c, rng)
	c.Assert(SameNodeID(id1, id2), Equals, false)
}

func (s *XLSuite) TestGoodNames(c *C) {
	rng := xr.MakeSimpleRNG()
	var count int = 3 + rng.Intn(16)
	for i := 0; i < count; i++ {
		s := s.noDotsOrDashes(rng)
		c.Assert(ValidEntityName(s), IsNil)
	}
}

func (d *XLSuite) TestXLatticePkt(c *C) {
	if VERBOSITY > 0 {
		fmt.Println("TEST_XLATTICE_PKT")
	}

	rng := xr.MakeSimpleRNG()

	myMsgN := uint64(rng.Int63())
	for myMsgN == 0 { // must not be zero
		myMsgN = uint64(rng.Int63())
	}

	id := make([]byte, 32) // sha3 length
	rng.NextBytes(id)      // random bytes

	seqBuf := new(bytes.Buffer)
	binary.Write(seqBuf, binary.LittleEndian, myMsgN)

	msgLen := 64 + rng.Intn(64)
	msg := make([]byte, msgLen)
	rng.NextBytes(msg) // fill with rubbish

	salt := make([]byte, 8)
	rng.NextBytes(salt) // still more rubbish

	digest := sha3.New256()
	digest.Write(id)
	digest.Write(seqBuf.Bytes())
	digest.Write(msg)
	digest.Write([]byte(salt))

	hash := digest.Sum(nil)

	// XXX This does not adhere to the rules: it has no Cmd field;
	// since it has a payload it must be a Put, and so the id is
	// also required and the Hash field should be a Sig instead, right?
	var pkt = XLatticeMsg{
		MsgN:    &myMsgN,
		Payload: msg,
		Salt:    salt,
		Hash:    hash,
	}

	// In each of these cases, the test proves that the field
	// was present; otherwise the 'empty' value (zero, nil, etc)
	// would have been returned.
	msgNOut := pkt.GetMsgN()
	c.Assert(msgNOut, Equals, myMsgN)

	msgOut := pkt.GetPayload()
	d.compareByteSlices(c, msgOut, msg)

	saltOut := pkt.GetSalt()
	d.compareByteSlices(c, saltOut, salt)

	hashOut := pkt.GetHash()
	d.compareByteSlices(c, hashOut, hash)
}