1 files changed, 296 insertions, 0 deletions
diff --git a/src/cmd/internal/gcprog/gcprog.go b/src/cmd/internal/gcprog/gcprog.go
new file mode 100644
index 0000000..eeea53d
--- /dev/null
+++ b/src/cmd/internal/gcprog/gcprog.go
@@ -0,0 +1,296 @@
+// 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
+}