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