...
Run Format

Source file src/cmd/internal/gcprog/gcprog.go

Documentation: cmd/internal/gcprog

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

View as plain text