gcprog.go

     1  // Copyright 2015 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Package gcprog implements an encoder for packed GC pointer bitmaps,
     6  // known as GC programs.
     7  //
     8  // # Program Format
     9  //
    10  // The GC program encodes a sequence of 0 and 1 bits indicating scalar or pointer words in an object.
    11  // The encoding is a simple Lempel-Ziv program, with codes to emit literal bits and to repeat the
    12  // last n bits c times.
    13  //
    14  // The possible codes are:
    15  //
    16  //	00000000: stop
    17  //	0nnnnnnn: emit n bits copied from the next (n+7)/8 bytes, least significant bit first
    18  //	10000000 n c: repeat the previous n bits c times; n, c are varints
    19  //	1nnnnnnn c: repeat the previous n bits c times; c is a varint
    20  //
    21  // The numbers n and c, when they follow a code, are encoded as varints
    22  // using the same encoding as encoding/binary's Uvarint.
    23  package gcprog
    24  
    25  import (
    26  	"fmt"
    27  	"io"
    28  )
    29  
    30  const progMaxLiteral = 127 // maximum n for literal n bit code
    31  
    32  // A Writer is an encoder for GC programs.
    33  //
    34  // The typical use of a Writer is to call Init, maybe call Debug,
    35  // make a sequence of Ptr, Advance, Repeat, and Append calls
    36  // to describe the data type, and then finally call End.
    37  type Writer struct {
    38  	writeByte func(byte)
    39  	index     int64
    40  	b         [progMaxLiteral]byte
    41  	nb        int
    42  	debug     io.Writer
    43  	debugBuf  []byte
    44  }
    45  
    46  // Init initializes w to write a new GC program
    47  // by calling writeByte for each byte in the program.
    48  func (w *Writer) Init(writeByte func(byte)) {
    49  	w.writeByte = writeByte
    50  }
    51  
    52  // Debug causes the writer to print a debugging trace to out
    53  // during future calls to methods like Ptr, Advance, and End.
    54  // It also enables debugging checks during the encoding.
    55  func (w *Writer) Debug(out io.Writer) {
    56  	w.debug = out
    57  }
    58  
    59  // BitIndex returns the number of bits written to the bit stream so far.
    60  func (w *Writer) BitIndex() int64 {
    61  	return w.index
    62  }
    63  
    64  // byte writes the byte x to the output.
    65  func (w *Writer) byte(x byte) {
    66  	if w.debug != nil {
    67  		w.debugBuf = append(w.debugBuf, x)
    68  	}
    69  	w.writeByte(x)
    70  }
    71  
    72  // End marks the end of the program, writing any remaining bytes.
    73  func (w *Writer) End() {
    74  	w.flushlit()
    75  	w.byte(0)
    76  	if w.debug != nil {
    77  		index := progbits(w.debugBuf)
    78  		if index != w.index {
    79  			println("gcprog: End wrote program for", index, "bits, but current index is", w.index)
    80  			panic("gcprog: out of sync")
    81  		}
    82  	}
    83  }
    84  
    85  // Ptr emits a 1 into the bit stream at the given bit index.
    86  // that is, it records that the index'th word in the object memory is a pointer.
    87  // Any bits between the current index and the new index
    88  // are set to zero, meaning the corresponding words are scalars.
    89  func (w *Writer) Ptr(index int64) {
    90  	if index < w.index {
    91  		println("gcprog: Ptr at index", index, "but current index is", w.index)
    92  		panic("gcprog: invalid Ptr index")
    93  	}
    94  	w.ZeroUntil(index)
    95  	if w.debug != nil {
    96  		fmt.Fprintf(w.debug, "gcprog: ptr at %d\n", index)
    97  	}
    98  	w.lit(1)
    99  }
   100  
   101  // ShouldRepeat reports whether it would be worthwhile to
   102  // use a Repeat to describe c elements of n bits each,
   103  // compared to just emitting c copies of the n-bit description.
   104  func (w *Writer) ShouldRepeat(n, c int64) bool {
   105  	// Should we lay out the bits directly instead of
   106  	// encoding them as a repetition? Certainly if count==1,
   107  	// since there's nothing to repeat, but also if the total
   108  	// size of the plain pointer bits for the type will fit in
   109  	// 4 or fewer bytes, since using a repetition will require
   110  	// flushing the current bits plus at least one byte for
   111  	// the repeat size and one for the repeat count.
   112  	return c > 1 && c*n > 4*8
   113  }
   114  
   115  // Repeat emits an instruction to repeat the description
   116  // of the last n words c times (including the initial description, c+1 times in total).
   117  func (w *Writer) Repeat(n, c int64) {
   118  	if n == 0 || c == 0 {
   119  		return
   120  	}
   121  	w.flushlit()
   122  	if w.debug != nil {
   123  		fmt.Fprintf(w.debug, "gcprog: repeat %d × %d\n", n, c)
   124  	}
   125  	if n < 128 {
   126  		w.byte(0x80 | byte(n))
   127  	} else {
   128  		w.byte(0x80)
   129  		w.varint(n)
   130  	}
   131  	w.varint(c)
   132  	w.index += n * c
   133  }
   134  
   135  // ZeroUntil adds zeros to the bit stream until reaching the given index;
   136  // that is, it records that the words from the most recent pointer until
   137  // the index'th word are scalars.
   138  // ZeroUntil is usually called in preparation for a call to Repeat, Append, or End.
   139  func (w *Writer) ZeroUntil(index int64) {
   140  	if index < w.index {
   141  		println("gcprog: Advance", index, "but index is", w.index)
   142  		panic("gcprog: invalid Advance index")
   143  	}
   144  	skip := (index - w.index)
   145  	if skip == 0 {
   146  		return
   147  	}
   148  	if skip < 4*8 {
   149  		if w.debug != nil {
   150  			fmt.Fprintf(w.debug, "gcprog: advance to %d by literals\n", index)
   151  		}
   152  		for i := int64(0); i < skip; i++ {
   153  			w.lit(0)
   154  		}
   155  		return
   156  	}
   157  
   158  	if w.debug != nil {
   159  		fmt.Fprintf(w.debug, "gcprog: advance to %d by repeat\n", index)
   160  	}
   161  	w.lit(0)
   162  	w.flushlit()
   163  	w.Repeat(1, skip-1)
   164  }
   165  
   166  // Append emits the given GC program into the current output.
   167  // The caller asserts that the program emits n bits (describes n words),
   168  // and Append panics if that is not true.
   169  func (w *Writer) Append(prog []byte, n int64) {
   170  	w.flushlit()
   171  	if w.debug != nil {
   172  		fmt.Fprintf(w.debug, "gcprog: append prog for %d ptrs\n", n)
   173  		fmt.Fprintf(w.debug, "\t")
   174  	}
   175  	n1 := progbits(prog)
   176  	if n1 != n {
   177  		panic("gcprog: wrong bit count in append")
   178  	}
   179  	// The last byte of the prog terminates the program.
   180  	// Don't emit that, or else our own program will end.
   181  	for i, x := range prog[:len(prog)-1] {
   182  		if w.debug != nil {
   183  			if i > 0 {
   184  				fmt.Fprintf(w.debug, " ")
   185  			}
   186  			fmt.Fprintf(w.debug, "%02x", x)
   187  		}
   188  		w.byte(x)
   189  	}
   190  	if w.debug != nil {
   191  		fmt.Fprintf(w.debug, "\n")
   192  	}
   193  	w.index += n
   194  }
   195  
   196  // progbits returns the length of the bit stream encoded by the program p.
   197  func progbits(p []byte) int64 {
   198  	var n int64
   199  	for len(p) > 0 {
   200  		x := p[0]
   201  		p = p[1:]
   202  		if x == 0 {
   203  			break
   204  		}
   205  		if x&0x80 == 0 {
   206  			count := x &^ 0x80
   207  			n += int64(count)
   208  			p = p[(count+7)/8:]
   209  			continue
   210  		}
   211  		nbit := int64(x &^ 0x80)
   212  		if nbit == 0 {
   213  			nbit, p = readvarint(p)
   214  		}
   215  		var count int64
   216  		count, p = readvarint(p)
   217  		n += nbit * count
   218  	}
   219  	if len(p) > 0 {
   220  		println("gcprog: found end instruction after", n, "ptrs, with", len(p), "bytes remaining")
   221  		panic("gcprog: extra data at end of program")
   222  	}
   223  	return n
   224  }
   225  
   226  // readvarint reads a varint from p, returning the value and the remainder of p.
   227  func readvarint(p []byte) (int64, []byte) {
   228  	var v int64
   229  	var nb uint
   230  	for {
   231  		c := p[0]
   232  		p = p[1:]
   233  		v |= int64(c&^0x80) << nb
   234  		nb += 7
   235  		if c&0x80 == 0 {
   236  			break
   237  		}
   238  	}
   239  	return v, p
   240  }
   241  
   242  // lit adds a single literal bit to w.
   243  func (w *Writer) lit(x byte) {
   244  	if w.nb == progMaxLiteral {
   245  		w.flushlit()
   246  	}
   247  	w.b[w.nb] = x
   248  	w.nb++
   249  	w.index++
   250  }
   251  
   252  // varint emits the varint encoding of x.
   253  func (w *Writer) varint(x int64) {
   254  	if x < 0 {
   255  		panic("gcprog: negative varint")
   256  	}
   257  	for x >= 0x80 {
   258  		w.byte(byte(0x80 | x))
   259  		x >>= 7
   260  	}
   261  	w.byte(byte(x))
   262  }
   263  
   264  // flushlit flushes any pending literal bits.
   265  func (w *Writer) flushlit() {
   266  	if w.nb == 0 {
   267  		return
   268  	}
   269  	if w.debug != nil {
   270  		fmt.Fprintf(w.debug, "gcprog: flush %d literals\n", w.nb)
   271  		fmt.Fprintf(w.debug, "\t%v\n", w.b[:w.nb])
   272  		fmt.Fprintf(w.debug, "\t%02x", byte(w.nb))
   273  	}
   274  	w.byte(byte(w.nb))
   275  	var bits uint8
   276  	for i := 0; i < w.nb; i++ {
   277  		bits |= w.b[i] << uint(i%8)
   278  		if (i+1)%8 == 0 {
   279  			if w.debug != nil {
   280  				fmt.Fprintf(w.debug, " %02x", bits)
   281  			}
   282  			w.byte(bits)
   283  			bits = 0
   284  		}
   285  	}
   286  	if w.nb%8 != 0 {
   287  		if w.debug != nil {
   288  			fmt.Fprintf(w.debug, " %02x", bits)
   289  		}
   290  		w.byte(bits)
   291  	}
   292  	if w.debug != nil {
   293  		fmt.Fprintf(w.debug, "\n")
   294  	}
   295  	w.nb = 0
   296  }
   297
View as plain text