diploma/bin/bin.go

package bin

import (
	"errors"
	"fmt"
	"io"
	"math"
)

const (
	varInt64SignFlag = 0b01000000
	maxReadAttempts  = 5
)

var (
	ErrNoSpace         = errors.New("no space")
	ErrIncompleteWrite = errors.New("incomplete write")

	ErrReadOverflow = errors.New("bin: reader returned 'n' > bufsize")
	// ErrNegativeReadCount shows 100% bug in the source reader
	ErrNegativeReadCount = errors.New("bin: reader returned negative 'n'")
)

// READ

func ReadUint16(src io.Reader) (num uint16, err error) {
	var (
		q   = 2
		arr = make([]byte, q)
	)
	n, err := src.Read(arr)
	if err != nil {
		return
	}
	if n != q {
		return 0, fmt.Errorf("read %d bytes only", n)
	}
	return GetUint16(arr), nil
}

func ReadUint24AsInt(src io.Reader) (num int, err error) {
	var (
		q   = 3
		arr = make([]byte, q)
	)
	n, err := src.Read(arr)
	if err != nil {
		return
	}
	if n != q {
		return 0, fmt.Errorf("read %d bytes only", n)
	}
	return GetUint24AsInt(arr), nil
}

func ReadUint32(src io.Reader) (num uint32, err error) {
	var (
		q   = 4
		arr = make([]byte, q)
	)
	n, err := src.Read(arr)
	if err != nil {
		return
	}
	if n != q {
		return 0, fmt.Errorf("read %d bytes only", n)
	}
	return GetUint32(arr), nil
}

func ReadUint64(src io.Reader) (num uint64, err error) {
	var (
		q   = 8
		arr = make([]byte, q)
	)
	n, err := src.Read(arr)
	if err != nil {
		return
	}
	if n != q {
		return 0, fmt.Errorf("read %d bytes only", n)
	}
	return GetUint64(arr), nil
}

func ReadFloat64(src io.Reader) (num float64, err error) {
	var (
		q   = 8
		arr = make([]byte, q)
	)
	n, err := src.Read(arr)
	if err != nil {
		return
	}
	if n != q {
		return 0, fmt.Errorf("read %d bytes only", n)
	}
	return GetFloat64(arr), nil
}

func ReadUnixtime(src io.Reader) (num int64, err error) {
	var (
		q   = 8
		arr = make([]byte, q)
	)
	n, err := src.Read(arr)
	if err != nil {
		return
	}
	if n != q {
		return 0, fmt.Errorf("read %d bytes only", n)
	}
	return int64(GetUint64(arr)), nil
}

// READ VAR

func ReadVarUint64(src io.Reader) (num uint64, n int, err error) {
	var (
		p = make([]byte, 1)
		b byte
	)
	for i := range 8 {
		_, err = src.Read(p)
		if err != nil {
			return
		}
		n++
		b = p[0]
		if b >= 128 {
			num |= uint64(b&127) << uint(i*7)
			return
		}
		num |= uint64(b) << uint(i*7)
	}
	_, err = src.Read(p)
	if err != nil {
		return
	}
	n++
	num |= uint64(p[0]) << 56
	return
}

// GET

func GetUint16(arr []byte) uint16 {
	return uint16(arr[0]) | (uint16(arr[1]) << 8)
}

func GetUint16AsInt(arr []byte) int {
	return int(arr[0]) | (int(arr[1]) << 8)
}

func GetUint24AsInt(arr []byte) int {
	return int(arr[0]) | (int(arr[1]) << 8) | (int(arr[2]) << 16)
}

func GetUint32(arr []byte) uint32 {
	return uint32(arr[0]) | (uint32(arr[1]) << 8) |
		(uint32(arr[2]) << 16) | (uint32(arr[3]) << 24)
}

func GetUint32AsInt64(arr []byte) int64 {
	u32 := uint32(arr[0]) | (uint32(arr[1]) << 8) |
		(uint32(arr[2]) << 16) | (uint32(arr[3]) << 24)
	return int64(u32)
}

func GetUint40(arr []byte) uint64 {
	return uint64(arr[0]) | (uint64(arr[1]) << 8) |
		(uint64(arr[2]) << 16) | (uint64(arr[3]) << 24) |
		(uint64(arr[4]) << 32)
}

func GetUint48(arr []byte) uint64 {
	return uint64(arr[0]) | (uint64(arr[1]) << 8) |
		(uint64(arr[2]) << 16) | (uint64(arr[3]) << 24) |
		(uint64(arr[4]) << 32) | (uint64(arr[5]) << 40)
}

func GetUint64(arr []byte) uint64 {
	return uint64(arr[0]) | (uint64(arr[1]) << 8) |
		(uint64(arr[2]) << 16) | (uint64(arr[3]) << 24) |
		(uint64(arr[4]) << 32) | (uint64(arr[5]) << 40) |
		(uint64(arr[6]) << 48) | (uint64(arr[7]) << 56)
}

func GetFloat32(arr []byte) float32 {
	return math.Float32frombits(GetUint32(arr))
}

func GetFloat64(arr []byte) float64 {
	return math.Float64frombits(GetUint64(arr))
}

func GetUnixtime(arr []byte) int64 {
	u32 := uint32(arr[0]) | (uint32(arr[1]) << 8) |
		(uint32(arr[2]) << 16) | (uint32(arr[3]) << 24)
	return int64(u32)
}

func GetVarUint64(arr []byte) (num uint64, n int, err error) {
	var b byte
	for i := range 8 {
		if i >= len(arr) {
			return 0, 0, io.EOF
		}
		b = arr[i]
		if b >= 128 {
			num |= uint64(b&127) << uint(i*7)
			return num, i + 1, nil
		}
		num |= uint64(b) << uint(i*7)
	}
	if len(arr) < 9 {
		return 0, 0, io.EOF
	}
	return num | uint64(arr[8])<<56, 9, nil
}

func ReverseGetVarUint64(arr []byte) (num uint64, n int, err error) {
	var (
		b byte
		j = len(arr) - 1
	)
	for i := range 8 {
		if j < 0 {
			return 0, 0, io.EOF
		}
		b = arr[j]
		if b >= 128 {
			num |= uint64(b&127) << uint(i*7)
			return num, i + 1, nil
		}
		num |= uint64(b) << uint(i*7)
		j--
	}
	if j < 0 {
		return 0, 0, io.EOF
	}
	return num | uint64(arr[j])<<56, 9, nil
}

func GetVarInt64(arr []byte) (num int64, n int, err error) {
	u64, n, err := GetVarUint64(arr)
	if err != nil {
		return
	}
	return DecodeZigZag(u64), n, nil
}

func ReverseGetVarInt64(arr []byte) (num int64, n int, err error) {
	u64, n, err := ReverseGetVarUint64(arr)
	if err != nil {
		return
	}
	return DecodeZigZag(u64), n, nil
}

// PUT

func PutUint16(arr []byte, num uint16) {
	arr[0] = byte(num)
	arr[1] = byte(num >> 8)
}

func PutIntAsUint16(arr []byte, num int) {
	arr[0] = byte(num)
	arr[1] = byte(num >> 8)
}

func PutIntAsUint24(arr []byte, num int) {
	arr[0] = byte(num)
	arr[1] = byte(num >> 8)
	arr[2] = byte(num >> 16)
}

func PutUint32(arr []byte, num uint32) {
	arr[0] = byte(num)
	arr[1] = byte(num >> 8)
	arr[2] = byte(num >> 16)
	arr[3] = byte(num >> 24)
}

func PutInt64AsUint32(arr []byte, num int64) {
	arr[0] = byte(num)
	arr[1] = byte(num >> 8)
	arr[2] = byte(num >> 16)
	arr[3] = byte(num >> 24)
}

func PutUint40(arr []byte, num uint64) {
	arr[0] = byte(num)
	arr[1] = byte(num >> 8)
	arr[2] = byte(num >> 16)
	arr[3] = byte(num >> 24)
	arr[4] = byte(num >> 32)
}

func PutUint48(arr []byte, num uint64) {
	arr[0] = byte(num)
	arr[1] = byte(num >> 8)
	arr[2] = byte(num >> 16)
	arr[3] = byte(num >> 24)
	arr[4] = byte(num >> 32)
	arr[5] = byte(num >> 40)
}

func PutUint64(arr []byte, num uint64) {
	arr[0] = byte(num)
	arr[1] = byte(num >> 8)
	arr[2] = byte(num >> 16)
	arr[3] = byte(num >> 24)
	arr[4] = byte(num >> 32)
	arr[5] = byte(num >> 40)
	arr[6] = byte(num >> 48)
	arr[7] = byte(num >> 56)
}

func PutFloat32(arr []byte, num float32) {
	PutUint32(arr, math.Float32bits(num))
}

func PutFloat64(arr []byte, num float64) {
	PutUint64(arr, math.Float64bits(num))
}

// WRITE

func WriteUint16(dst io.Writer, num uint16) error {
	arr := []byte{
		byte(num),
		byte(num >> 8),
	}
	n, err := dst.Write(arr)
	if err != nil {
		return err
	}
	if n != 2 {
		return ErrIncompleteWrite
	}
	return err
}

func WriteUint32(dst io.Writer, num uint32) error {
	arr := []byte{
		byte(num),
		byte(num >> 8),
		byte(num >> 16),
		byte(num >> 24),
	}
	n, err := dst.Write(arr)
	if err != nil {
		return err
	}
	if n != 4 {
		return ErrIncompleteWrite
	}
	return err
}

func WriteFloat64(dst io.Writer, num float64) error {
	arr := make([]byte, 8)
	PutUint64(arr, math.Float64bits(num))
	n, err := dst.Write(arr)
	if err != nil {
		return err
	}
	if n != 2 {
		return ErrIncompleteWrite
	}
	return err
}

// WRITE VAR

func WriteVarUint64(dst io.Writer, num uint64) (int, error) {
	arr := make([]byte, 9)
	for i := range 8 {
		arr[i] = byte(num & 127)
		num >>= 7
		if num == 0 {
			arr[i] |= 128
			size := i + 1
			n, err := dst.Write(arr[:size])
			if err != nil {
				return n, err
			}
			if n != size {
				return n, ErrIncompleteWrite
			}
			return size, nil
		}
	}
	arr[8] = byte(num)
	n, err := dst.Write(arr)
	if err != nil {
		return n, err
	}
	if n != 9 {
		return n, ErrIncompleteWrite
	}
	return 9, nil
}

func PutVarUint64(arr []byte, num uint64) (int, error) {
	for i := range 8 {
		if i >= len(arr) {
			return 0, ErrNoSpace
		}
		arr[i] = byte(num & 127)
		num >>= 7
		if num == 0 {
			arr[i] |= 128
			return i + 1, nil
		}
	}
	if len(arr) < 9 {
		return 0, ErrNoSpace
	}
	arr[8] = byte(num)
	return 9, nil
}

func ReversePutVarUint64(arr []byte, num uint64) (int, error) {
	var tmp [9]byte
	for i := range 8 {
		tmp[i] = byte(num & 127)
		num >>= 7
		if num == 0 {
			tmp[i] |= 128
			n := i + 1
			if len(arr) < n {
				return 0, ErrNoSpace
			}
			for j := i; j >= 0; j-- {
				arr[i-j] = tmp[j]
			}
			return n, nil
		}
	}
	tmp[8] = byte(num)
	n := 9
	if len(arr) < n {
		return 0, ErrNoSpace
	}
	for j := 8; j >= 0; j-- {
		arr[8-j] = tmp[j]
	}
	return n, nil
}

func PutVarUint64AtEnd(arr []byte, num uint64) (int, error) {
	var (
		tmp [9]byte
		n   int
	)
	for i := range 8 {
		tmp[i] = byte(num & 127)
		num >>= 7
		if num == 0 {
			tmp[i] |= 128
			n = i + 1
			break
		}
	}
	if n == 0 {
		tmp[8] = byte(num)
		n = 9
	}
	if len(arr) < n {
		return 0, ErrNoSpace
	}
	j := len(arr) - n
	for i := range n {
		arr[j] = tmp[i]
		j++
	}
	return n, nil
}

func PutVarInt64(arr []byte, x int64) (int, error) {
	return PutVarUint64(arr, EncodeZigZag(x))
}

func PutVarInt64AtEnd(arr []byte, x int64) (int, error) {
	return PutVarUint64AtEnd(arr, EncodeZigZag(x))
}

func ReversePutVarInt64(arr []byte, x int64) (int, error) {
	return ReversePutVarUint64(arr, EncodeZigZag(x))
}

type KeyComparator interface {
	CompareTo(int) int
}

func BinarySearch(qty int, keyComparator KeyComparator) (elemIdx int, isFound bool) {
	if qty == 0 {
		return
	}
	a := 0
	b := qty - 1
	for {
		var (
			elemIdx = (b-a)/2 + a
			code    = keyComparator.CompareTo(elemIdx)
		)

		if code == 1 {
			a = elemIdx + 1
			if a > b {
				return elemIdx + 1, false
			}
		} else if code == -1 {
			b = elemIdx - 1
			if b < a {
				return elemIdx, false
			}
		} else {
			return elemIdx, true
		}
	}
}

func DeleteReverseArrElem(arr []byte, qty int, elemSize int, idx int) {
	dstIdx := len(arr) - idx*elemSize - 1
	srcIdx := dstIdx - elemSize

	end := len(arr) - qty*elemSize

	for ; srcIdx >= end; srcIdx-- {
		arr[dstIdx] = arr[srcIdx]
		dstIdx--
	}

	for i := end; i < end+elemSize; i++ {
		arr[i] = 0
	}
}

// ZigZag

// ZigZag encoding: int64 -> uint64
func EncodeZigZag(x int64) uint64 {
	return uint64(x<<1) ^ uint64(x>>63)
}

// ZigZag decoding: uint64 -> int64
func DecodeZigZag(u uint64) int64 {
	return int64(u>>1) ^ -(int64(u & 1))
}

func ReadN(r io.Reader, n int) (_ []byte, err error) {
	if n < 0 {
		err = fmt.Errorf("wrong n=%d", n)
		return
	}
	buf := make([]byte, n)
	err = ReadNInto(r, buf)
	if err != nil {
		return
	}
	return buf, nil
}

func ReadNInto(r io.Reader, buf []byte) (err error) {
	if len(buf) == 0 {
		return
	}

	var q, total, readAttempts int

	for readAttempts < maxReadAttempts {
		bufsize := len(buf) - total
		q, err = r.Read(buf[total:])
		if q == bufsize {
			return nil
		}
		if err != nil {
			return
		}
		if q > bufsize {
			err = ErrReadOverflow
			return
		}
		if q < 0 {
			err = ErrNegativeReadCount
			return
		}
		if q == 0 {
			readAttempts++
		} else {
			total += q
		}
	}
	err = io.ErrNoProgress
	return
}

func CalcVarUint64Length(num uint64) int {
	for i := range 8 {
		num >>= 7
		if num == 0 {
			return i + 1
		}
	}
	return 9
}

func CalcVarInt64Length(num int64) int {
	u64 := EncodeZigZag(num)
	for i := range 8 {
		u64 >>= 7
		if u64 == 0 {
			return i + 1
		}
	}
	return 9
}