// 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 }