internal/gcprog/gcprog.go

// Copyright 2015 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 gcprog implements an encoder for packed GC pointer bitmaps,
// known as GC programs.
//
// Program Format
//
// The GC program encodes a sequence of 0 and 1 bits indicating scalar or pointer words in an object.
// The encoding is a simple Lempel-Ziv program, with codes to emit literal bits and to repeat the
// last n bits c times.
//
// The possible codes are:
//
//	00000000: stop
//	0nnnnnnn: emit n bits copied from the next (n+7)/8 bytes, least significant bit first
//	10000000 n c: repeat the previous n bits c times; n, c are varints
//	1nnnnnnn c: repeat the previous n bits c times; c is a varint
//
// The numbers n and c, when they follow a code, are encoded as varints
// using the same encoding as encoding/binary's Uvarint.
//
package gcprog

import (
	"fmt"
	"io"
)

const progMaxLiteral = 127 // maximum n for literal n bit code

// A Writer is an encoder for GC programs.
//
// The typical use of a Writer is to call Init, maybe call Debug,
// make a sequence of Ptr, Advance, Repeat, and Append calls
// to describe the data type, and then finally call End.
type Writer struct {
	writeByte func(byte)
	index     int64
	b         [progMaxLiteral]byte
	nb        int
	debug     io.Writer
	debugBuf  []byte
}

// Init initializes w to write a new GC program
// by calling writeByte for each byte in the program.
func (w *Writer) Init(writeByte func(byte)) {
	w.writeByte = writeByte
}

// Debug causes the writer to print a debugging trace to out
// during future calls to methods like Ptr, Advance, and End.
// It also enables debugging checks during the encoding.
func (w *Writer) Debug(out io.Writer) {
	w.debug = out
}

// BitIndex returns the number of bits written to the bit stream so far.
func (w *Writer) BitIndex() int64 {
	return w.index
}

// byte writes the byte x to the output.
func (w *Writer) byte(x byte) {
	if w.debug != nil {
		w.debugBuf = append(w.debugBuf, x)
	}
	w.writeByte(x)
}

// End marks the end of the program, writing any remaining bytes.
func (w *Writer) End() {
	w.flushlit()
	w.byte(0)
	if w.debug != nil {
		index := progbits(w.debugBuf)
		if index != w.index {
			println("gcprog: End wrote program for", index, "bits, but current index is", w.index)
			panic("gcprog: out of sync")
		}
	}
}

// Ptr emits a 1 into the bit stream at the given bit index.
// that is, it records that the index'th word in the object memory is a pointer.
// Any bits between the current index and the new index
// are set to zero, meaning the corresponding words are scalars.
func (w *Writer) Ptr(index int64) {
	if index < w.index {
		println("gcprog: Ptr at index", index, "but current index is", w.index)
		panic("gcprog: invalid Ptr index")
	}
	w.ZeroUntil(index)
	if w.debug != nil {
		fmt.Fprintf(w.debug, "gcprog: ptr at %d\n", index)
	}
	w.lit(1)
}

// ShouldRepeat reports whether it would be worthwhile to
// use a Repeat to describe c elements of n bits each,
// compared to just emitting c copies of the n-bit description.
func (w *Writer) ShouldRepeat(n, c int64) bool {
	// Should we lay out the bits directly instead of
	// encoding them as a repetition? Certainly if count==1,
	// since there's nothing to repeat, but also if the total
	// size of the plain pointer bits for the type will fit in
	// 4 or fewer bytes, since using a repetition will require
	// flushing the current bits plus at least one byte for
	// the repeat size and one for the repeat count.
	return c > 1 && c*n > 4*8
}

// Repeat emits an instruction to repeat the description
// of the last n words c times (including the initial description, c+1 times in total).
func (w *Writer) Repeat(n, c int64) {
	if n == 0 || c == 0 {
		return
	}
	w.flushlit()
	if w.debug != nil {
		fmt.Fprintf(w.debug, "gcprog: repeat %d  %d\n", n, c)
	}
	if n < 128 {
		w.byte(0x80 | byte(n))
	} else {
		w.byte(0x80)
		w.varint(n)
	}
	w.varint(c)
	w.index += n * c
}

// ZeroUntil adds zeros to the bit stream until reaching the given index;
// that is, it records that the words from the most recent pointer until
// the index'th word are scalars.
// ZeroUntil is usually called in preparation for a call to Repeat, Append, or End.
func (w *Writer) ZeroUntil(index int64) {
	if index < w.index {
		println("gcprog: Advance", index, "but index is", w.index)
		panic("gcprog: invalid Advance index")
	}
	skip := (index - w.index)
	if skip == 0 {
		return
	}
	if skip < 4*8 {
		if w.debug != nil {
			fmt.Fprintf(w.debug, "gcprog: advance to %d by literals\n", index)
		}
		for i := int64(0); i < skip; i++ {
			w.lit(0)
		}
		return
	}

	if w.debug != nil {
		fmt.Fprintf(w.debug, "gcprog: advance to %d by repeat\n", index)
	}
	w.lit(0)
	w.flushlit()
	w.Repeat(1, skip-1)
}

// Append emits the given GC program into the current output.
// The caller asserts that the program emits n bits (describes n words),
// and Append panics if that is not true.
func (w *Writer) Append(prog []byte, n int64) {
	w.flushlit()
	if w.debug != nil {
		fmt.Fprintf(w.debug, "gcprog: append prog for %d ptrs\n", n)
		fmt.Fprintf(w.debug, "\t")
	}
	n1 := progbits(prog)
	if n1 != n {
		panic("gcprog: wrong bit count in append")
	}
	// The last byte of the prog terminates the program.
	// Don't emit that, or else our own program will end.
	for i, x := range prog[:len(prog)-1] {
		if w.debug != nil {
			if i > 0 {
				fmt.Fprintf(w.debug, " ")
			}
			fmt.Fprintf(w.debug, "%02x", x)
		}
		w.byte(x)
	}
	if w.debug != nil {
		fmt.Fprintf(w.debug, "\n")
	}
	w.index += n
}

// progbits returns the length of the bit stream encoded by the program p.
func progbits(p []byte) int64 {
	var n int64
	for len(p) > 0 {
		x := p[0]
		p = p[1:]
		if x == 0 {
			break
		}
		if x&0x80 == 0 {
			count := x &^ 0x80
			n += int64(count)
			p = p[(count+7)/8:]
			continue
		}
		nbit := int64(x &^ 0x80)
		if nbit == 0 {
			nbit, p = readvarint(p)
		}
		var count int64
		count, p = readvarint(p)
		n += nbit * count
	}
	if len(p) > 0 {
		println("gcprog: found end instruction after", n, "ptrs, with", len(p), "bytes remaining")
		panic("gcprog: extra data at end of program")
	}
	return n
}

// readvarint reads a varint from p, returning the value and the remainder of p.
func readvarint(p []byte) (int64, []byte) {
	var v int64
	var nb uint
	for {
		c := p[0]
		p = p[1:]
		v |= int64(c&^0x80) << nb
		nb += 7
		if c&0x80 == 0 {
			break
		}
	}
	return v, p
}

// lit adds a single literal bit to w.
func (w *Writer) lit(x byte) {
	if w.nb == progMaxLiteral {
		w.flushlit()
	}
	w.b[w.nb] = x
	w.nb++
	w.index++
}

// varint emits the varint encoding of x.
func (w *Writer) varint(x int64) {
	if x < 0 {
		panic("gcprog: negative varint")
	}
	for x >= 0x80 {
		w.byte(byte(0x80 | x))
		x >>= 7
	}
	w.byte(byte(x))
}

// flushlit flushes any pending literal bits.
func (w *Writer) flushlit() {
	if w.nb == 0 {
		return
	}
	if w.debug != nil {
		fmt.Fprintf(w.debug, "gcprog: flush %d literals\n", w.nb)
		fmt.Fprintf(w.debug, "\t%v\n", w.b[:w.nb])
		fmt.Fprintf(w.debug, "\t%02x", byte(w.nb))
	}
	w.byte(byte(w.nb))
	var bits uint8
	for i := 0; i < w.nb; i++ {
		bits |= w.b[i] << uint(i%8)
		if (i+1)%8 == 0 {
			if w.debug != nil {
				fmt.Fprintf(w.debug, " %02x", bits)
			}
			w.byte(bits)
			bits = 0
		}
	}
	if w.nb%8 != 0 {
		if w.debug != nil {
			fmt.Fprintf(w.debug, " %02x", bits)
		}
		w.byte(bits)
	}
	if w.debug != nil {
		fmt.Fprintf(w.debug, "\n")
	}
	w.nb = 0
}