// This optimized clz32 algorithm is from:
// 	 http://embeddedgurus.com/state-space/2014/09/
// 	 		fast-deterministic-and-portable-counting-leading-zeros/
540292
func clz32(x uint32) uint8 {
	var n uint8

	if x >= (1 << 16) {
		if x >= (1 << 24) {
			if x >= (1 << 28) {
				n = 28
			} else {
				n = 24
			}
		} else {
			if x >= (1 << 20) {
				n = 20
			} else {
				n = 16
			}
		}
	} else {
		if x >= (1 << 8) {
			if x >= (1 << 12) {
				n = 12
			} else {
				n = 8
			}
		} else {
			if x >= (1 << 4) {
				n = 4
			} else {
				n = 0
			}
		}
	}
	return clzLookup[x>>n] - n
}
326350
func FastBase58DecodingAlphabet(str string, alphabet *Alphabet) ([]byte, error) {
	if len(str) == 0 {
		return nil, fmt.Errorf("zero length string")
	}

	var (
		t        uint64
		zmask, c uint32
		zcount   int

		b58u  = []rune(str)
		b58sz = len(b58u)

		outisz    = (b58sz + 3) / 4 // check to see if we need to change this buffer size to optimize
		binu      = make([]byte, (b58sz+3)*3)
		bytesleft = b58sz % 4

		zero = rune(alphabet.encode[0])
	)

	if bytesleft > 0 {
		zmask = (0xffffffff << uint32(bytesleft*8))
	} else {
		bytesleft = 4
	}

	var outi = make([]uint32, outisz)

	for i := 0; i < b58sz && b58u[i] == zero; i++ {
		zcount++
	}

	for _, r := range b58u {
		if r > 127 {
			return nil, fmt.Errorf("High-bit set on invalid digit")
		}
		if alphabet.decode[r] == -1 {
			return nil, fmt.Errorf("Invalid base58 digit (%q)", r)
		}

		c = uint32(alphabet.decode[r])

		for j := (outisz - 1); j >= 0; j-- {
			t = uint64(outi[j])*58 + uint64(c)
			c = uint32(t>>32) & 0x3f
			outi[j] = uint32(t & 0xffffffff)
		}

		if c > 0 {
			return nil, fmt.Errorf("Output number too big (carry to the next int32)")
		}

		if outi[0]&zmask != 0 {
			return nil, fmt.Errorf("Output number too big (last int32 filled too far)")
		}
	}

	// the nested for-loop below is the same as the original code:
	// switch (bytesleft) {
	// 	case 3:
	// 		*(binu++) = (outi[0] & 0xff0000) >> 16;
	// 		//-fallthrough
	// 	case 2:
	// 		*(binu++) = (outi[0] & 0xff00) >>  8;
	// 		//-fallthrough
	// 	case 1:
	// 		*(binu++) = (outi[0] & 0xff);
	// 		++j;
	// 		//-fallthrough
	// 	default:
	// 		break;
	// }
	//
	// for (; j < outisz; ++j)
	// {
	// 	*(binu++) = (outi[j] >> 0x18) & 0xff;
	// 	*(binu++) = (outi[j] >> 0x10) & 0xff;
	// 	*(binu++) = (outi[j] >>    8) & 0xff;
	// 	*(binu++) = (outi[j] >>    0) & 0xff;
	// }
	var j, cnt int
	for j, cnt = 0, 0; j < outisz; j++ {
		for mask := byte(bytesleft-1) * 8; mask <= 0x18; mask, cnt = mask-8, cnt+1 {
			binu[cnt] = byte(outi[j] >> mask)
		}
		if j == 0 {
			bytesleft = 4 // because it could be less than 4 the first time through
		}
	}

	for n, v := range binu {
		if v > 0 {
			start := n - zcount
			if start < 0 {
				start = 0
			}
			return binu[start:cnt], nil
		}
	}
	return binu[:cnt], nil
}
32117
func (db *RedisDB) ZScore(k, member string) (float64, error) {
	db.master.Lock()
	defer db.master.Unlock()
	if !db.exists(k) {
		return 0, ErrKeyNotFound
	}
	if db.t(k) != "zset" {
		return 0, ErrWrongType
	}
	return db.ssetScore(k, member), nil
}
1238969
func ZigZagDelta(in, out []int32) {
	offset := int32(0)

	for i, v := range in {
		n := v - offset
		out[i] = (n << 1) ^ (n >> 31)
		offset = v
	}
}
552601
func benchmark32s(n int) {
	//var hashes = make(Uint32Slice, n)
	const nbytes = 16384 // fix
	bs := make([]byte, nbytes, nbytes)
	bs = bs[:]
	//fp20 := make([]byte, 20, 20)
	Hf2 = "nullhash"
	for _, ksiz := range keySizes {
		if ksiz == 512 {
			n = n / 10
		}
		bs = bs[:ksiz]
		//hashes = make(Uint32Slice, n, n)
		//hashes = hashes[:]
		//fmt.Printf("ksiz=%d, len(bs)=%d\n", ksiz, len(bs))
		pn := hrff.Int64{int64(n), ""}
		ps := hrff.Int64{int64(n * ksiz), "B"}
		//fmt.Printf("benchmark32s: gen n=%d, n=%h, keySize=%d, size=%h\n", n, pn, ksiz, ps)
		if false {
			_ = gomap.Hash64(bs, 0)
			_ = aeshash.Hash(bs, 0)
		}
		start, stop := time.Now(), time.Now()
		switch ksiz {
		case 4:
			start = time.Now()
			for i := 0; i < n; i++ {
				_ = aeshash.Hash(bs, 0)
				// sha1160.Reset()
				// sha1160.Write(bs)
				// fp20 = fp20[0:0]
				// fp20 = sha1160.Sum(fp20)
				// _ = uint64(fp20[0])<<56 | uint64(fp20[1])<<48 | uint64(fp20[2])<<40 | uint64(fp20[3])<<32 |
				// 	uint64(fp20[4])<<24 | uint64(fp20[5])<<16 | uint64(fp20[6])<<8  | uint64(fp20[7])<<0
				//k224.Reset()
				//k224.Write(bs)
				//_ = k224.Sum(nil)
				//bs[0], bs[1], bs[2], bs[3] = byte(i), byte(i>>8), byte(i>>16), byte(i>>24)
				//_, _ = jenkins.Jenkins364(bs, 0, 0, 0)
				//_ = jenkins.Hash232(bs, 0)
				//_, _ = jenkins.Jenkins364(bs, 0, 0, 0)
				//_ = gomap.Hash64(bs, 0)
				//_ =  nhf64.Hash64S(bs, 0) // chnage below too
				//nh.Reset()
				//nh.Write(bs)
				//_ = nh.Sum64()
				//Hashf(bs, 0)
				//_ = siphash.Hash(0, 0, bs)
				//hashes[i] = h
				//fmt.Printf("i=%d, 0x%08x, h=0x%08x\n", i, i, h)
				//hashes[i] = h
				//fmt.Printf("i=%d, 0x%08x, h=0x%08x\n", i, i, h)
			}
			stop = time.Now()
		default:
			start = time.Now()
			for i := 0; i < n; i++ {
				// sha1160.Reset()
				// sha1160.Write(bs)
				// fp20 = fp20[0:0]
				// fp20 = sha1160.Sum(fp20)
				// _ = uint64(fp20[0])<<56 | uint64(fp20[1])<<48 | uint64(fp20[2])<<40 | uint64(fp20[3])<<32 |
				// 	uint64(fp20[4])<<24 | uint64(fp20[5])<<16 | uint64(fp20[6])<<8  | uint64(fp20[7])<<0
				_ = aeshash.Hash(bs, 0)
				//k224.Reset()
				//k224.Write(bs)
				//_ = k224.Sum(nil)
				//bs[0], bs[1], bs[2], bs[3], bs[4], bs[5], bs[6], bs[7] = byte(i), byte(i>>8), byte(i>>16), byte(i>>24), byte(i>>32), byte(i>>40), byte(i>>48), byte(i>>56)
				//_, _ = jenkins.Jenkins364(bs, 0, 0, 0)
				//_ = aeshash.Hash(bs, 0)
				//_ = gomap.Hash64(bs, 0)
				//_ = siphash.Hash(0, 0, bs)
				//_ =  nhf64.Hash64S(bs, 0)
				//nh.Reset()
				//nh.Write(bs)
				//_ = nh.Sum64()
				//Hashf(bs, 0)
			}
			stop = time.Now()
		}
		d := tdiff(start, stop)
		hsec := hrff.Float64{(float64(n) / d.Seconds()), "hashes/sec"}
		bsec := hrff.Float64{(float64(n) * float64(ksiz) / d.Seconds()), "B/sec"}
		//fmt.Printf("benchmark32s: %h\n", hsec)
		//fmt.Printf("benchmark32s: %.2h\n\n", bsec)
		fmt.Printf("\tksize=%d, n=%h, size=%h, %h, %.1h, time=%v\n", ksiz, pn, ps, hsec, bsec, d)
	}
	return

	fmt.Printf("benchmark32s: sort n=%d\n", n)
	//hashes.Sort()
	/*
		for i := 0; i < n; i++ {
			fmt.Printf("i=%d, 0x%08x, h=0x%08x\n", i, i, hashes[i])
		}
	*/
	fmt.Printf("benchmark32s: dup check n=%d\n", n)
	//dups, mrun := checkForDups32(hashes)
	//fmt.Printf("benchmark32: dups=%d, mrun=%d\n", dups, mrun)
}
691653
func OptimalK(fpRate float64) uint {
	return uint(math.Ceil(math.Log2(1 / fpRate)))
}
460307
func (*And) optimizeReplacement(its []graph.Iterator) graph.Iterator {
	// If we were created with no SubIterators, we're as good as Null.
	if len(its) == 0 {
		return NewNull()
	}
	if len(its) == 1 {
		// When there's only one iterator, there's only one choice.
		return its[0]
	}
	// If any of our subiterators, post-optimization, are also Null, then
	// there's no point in continuing the branch, we will have no results
	// and we are null as well.
	if hasAnyNullIterators(its) {
		return NewNull()
	}

	// If we have one useful iterator, use that.
	it := hasOneUsefulIterator(its)
	if it != nil {
		return it
	}
	return nil
}
343678
func TrailingZeros16(x uint16) (n int) {
	if x == 0 {
		return 16
	}
	// see comment in TrailingZeros64
	return int(deBruijn32tab[uint32(x&-x)*deBruijn32>>(32-5)])
}
627962
func is_spacez(b []byte, i int) bool {
	//return is_space(b, i) || is_breakz(b, i)
	return ( // is_space:
	b[i] == ' ' ||
		// is_breakz:
		b[i] == '\r' || // CR (#xD)
		b[i] == '\n' || // LF (#xA)
		b[i] == 0xC2 && b[i+1] == 0x85 || // NEL (#x85)
		b[i] == 0xE2 && b[i+1] == 0x80 && b[i+2] == 0xA8 || // LS (#x2028)
		b[i] == 0xE2 && b[i+1] == 0x80 && b[i+2] == 0xA9 || // PS (#x2029)
		b[i] == 0)
}
93450
func FnGetAZs(name string, input interface{}, template interface{}) interface{} {

	// Check the input is a string
	if region, ok := input.(string); ok {
		if region == "" {
			region = "us-east-1"
		}

		if azs, ok := AZs[region]; ok {
			return azs
		} else {
			//assume 3 AZs per region
			return buildAZs(region, "a", "b", "c")
		}
	}

	return nil
}
10257
func cpIncr(bz []byte) (ret []byte) {
	ret = cp(bz)
	for i := len(bz) - 1; i >= 0; i-- {
		if ret[i] < byte(0xFF) {
			ret[i]++
			return
		}
		ret[i] = byte(0x00)
		if i == 0 {
			return append(ret, 0x00)
		}
	}
	return []byte{0x00}
}
549329
func nlz1a(x uint32) uint32 {
	var n uint32 = 0
	if x <= 0 {
		return (^x >> 26) & 32
	}

	n = 1

	if (x >> 16) == 0 {
		n = n + 16
		x = x << 16
	}
	if (x >> 24) == 0 {
		n = n + 8
		x = x << 8
	}
	if (x >> 28) == 0 {
		n = n + 4
		x = x << 4
	}
	if (x >> 30) == 0 {
		n = n + 2
		x = x << 2
	}
	n = n - (x >> 31)
	return n
}
1301236
func (r *Redis) ZScan(key string, cursor uint64, pattern string, count int) (uint64, []string, error) {
	args := packArgs("ZSCAN", key, cursor)
	if pattern != "" {
		args = append(args, "MATCH", pattern)
	}
	if count > 0 {
		args = append(args, "COUNT", count)
	}
	rp, err := r.ExecuteCommand(args...)
	if err != nil {
		return 0, nil, err
	}
	first, err := rp.Multi[0].StringValue()
	if err != nil {
		return 0, nil, err
	}
	next, err := strconv.ParseUint(first, 10, 64)
	if err != nil {
		return 0, nil, err
	}
	list, err := rp.Multi[1].ListValue()
	return next, list, err
}
1204560
func Linear(factor time.Duration) Algorithm {
	return func(attempt uint) time.Duration {
		return (factor * time.Duration(attempt))
	}
}
858401
func (m *Miniredis) cmdZpopmax(reverse bool) server.Cmd {
	return func(c *server.Peer, cmd string, args []string) {
		if len(args) < 1 {
			setDirty(c)
			c.WriteError(errWrongNumber(cmd))
			return
		}
		if !m.handleAuth(c) {
			return
		}

		key := args[0]
		count := 1
		var err error
		if len(args) > 1 {
			count, err = strconv.Atoi(args[1])

			if err != nil {
				setDirty(c)
				c.WriteError(msgInvalidInt)
				return
			}
		}

		withScores := true
		if len(args) > 2 {
			c.WriteError(msgSyntaxError)
			return
		}

		withTx(m, c, func(c *server.Peer, ctx *connCtx) {
			db := m.db(ctx.selectedDB)

			if !db.exists(key) {
				c.WriteLen(0)
				return
			}

			if db.t(key) != "zset" {
				c.WriteError(ErrWrongType.Error())
				return
			}

			members := db.ssetMembers(key)
			if reverse {
				reverseSlice(members)
			}
			rs, re := redisRange(len(members), 0, count-1, false)
			if withScores {
				c.WriteLen((re - rs) * 2)
			} else {
				c.WriteLen(re - rs)
			}
			for _, el := range members[rs:re] {
				c.WriteBulk(el)
				if withScores {
					c.WriteBulk(formatFloat(db.ssetScore(key, el)))
				}
				db.ssetRem(key, el)
			}
		})
	}
}
797728
func CountLeadZero32(value uint32) (uint) {
    var count uint = 0

    if (value & 0xFFFF0000) == 0 {
        count += 16;
        value <<= 16;
    }
    if (value & 0xFF000000) == 0 {
        count += 8;
        value <<= 8;
    }
    if (value & 0xF0000000) == 0 {
        count += 4;
        value <<= 4;
    }
    if (value & 0x30000000) == 0 {
        count += 2;
        value <<= 2;
    }
    if (value & 0x10000000) == 0 {
        count++;
        value <<= 1;
    }
    if (value & 0x10000000) == 0 {
        count++;
    }

    return count
}
1182526
func (c *Client) ZRemRangeByScore(key string, min interface{}, max interface{}) (int64, error) {
	var ret int64

	err := c.command(
		&ret,
		[]byte("ZREMRANGEBYSCORE"),
		[]byte(key),
		to.Bytes(min),
		to.Bytes(max),
	)

	return ret, err
}