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  // byte writes the byte x to the output.
    60  func (w *Writer) byte(x byte) {
    61  	if w.debug != nil {
    62  		w.debugBuf = append(w.debugBuf, x)
    63  	}
    64  	w.writeByte(x)
    65  }
    66  
    67  // End marks the end of the program, writing any remaining bytes.
    68  func (w *Writer) End() {
    69  	w.flushlit()
    70  	w.byte(0)
    71  	if w.debug != nil {
    72  		index := progbits(w.debugBuf)
    73  		if index != w.index {
    74  			println("gcprog: End wrote program for", index, "bits, but current index is", w.index)
    75  			panic("gcprog: out of sync")
    76  		}
    77  	}
    78  }
    79  
    80  // Ptr emits a 1 into the bit stream at the given bit index.
    81  // that is, it records that the index'th word in the object memory is a pointer.
    82  // Any bits between the current index and the new index
    83  // are set to zero, meaning the corresponding words are scalars.
    84  func (w *Writer) Ptr(index int64) {
    85  	if index < w.index {
    86  		println("gcprog: Ptr at index", index, "but current index is", w.index)
    87  		panic("gcprog: invalid Ptr index")
    88  	}
    89  	w.ZeroUntil(index)
    90  	if w.debug != nil {
    91  		fmt.Fprintf(w.debug, "gcprog: ptr at %d\n", index)
    92  	}
    93  	w.lit(1)
    94  }
    95  
    96  // Repeat emits an instruction to repeat the description
    97  // of the last n words c times (including the initial description, c+1 times in total).
    98  func (w *Writer) Repeat(n, c int64) {
    99  	if n == 0 || c == 0 {
   100  		return
   101  	}
   102  	w.flushlit()
   103  	if w.debug != nil {
   104  		fmt.Fprintf(w.debug, "gcprog: repeat %d × %d\n", n, c)
   105  	}
   106  	if n < 128 {
   107  		w.byte(0x80 | byte(n))
   108  	} else {
   109  		w.byte(0x80)
   110  		w.varint(n)
   111  	}
   112  	w.varint(c)
   113  	w.index += n * c
   114  }
   115  
   116  // ZeroUntil adds zeros to the bit stream until reaching the given index;
   117  // that is, it records that the words from the most recent pointer until
   118  // the index'th word are scalars.
   119  // ZeroUntil is usually called in preparation for a call to Repeat, Append, or End.
   120  func (w *Writer) ZeroUntil(index int64) {
   121  	if index < w.index {
   122  		println("gcprog: Advance", index, "but index is", w.index)
   123  		panic("gcprog: invalid Advance index")
   124  	}
   125  	skip := (index - w.index)
   126  	if skip == 0 {
   127  		return
   128  	}
   129  	if skip < 4*8 {
   130  		if w.debug != nil {
   131  			fmt.Fprintf(w.debug, "gcprog: advance to %d by literals\n", index)
   132  		}
   133  		for i := int64(0); i < skip; i++ {
   134  			w.lit(0)
   135  		}
   136  		return
   137  	}
   138  
   139  	if w.debug != nil {
   140  		fmt.Fprintf(w.debug, "gcprog: advance to %d by repeat\n", index)
   141  	}
   142  	w.lit(0)
   143  	w.flushlit()
   144  	w.Repeat(1, skip-1)
   145  }
   146  
   147  // progbits returns the length of the bit stream encoded by the program p.
   148  func progbits(p []byte) int64 {
   149  	var n int64
   150  	for len(p) > 0 {
   151  		x := p[0]
   152  		p = p[1:]
   153  		if x == 0 {
   154  			break
   155  		}
   156  		if x&0x80 == 0 {
   157  			count := x &^ 0x80
   158  			n += int64(count)
   159  			p = p[(count+7)/8:]
   160  			continue
   161  		}
   162  		nbit := int64(x &^ 0x80)
   163  		if nbit == 0 {
   164  			nbit, p = readvarint(p)
   165  		}
   166  		var count int64
   167  		count, p = readvarint(p)
   168  		n += nbit * count
   169  	}
   170  	if len(p) > 0 {
   171  		println("gcprog: found end instruction after", n, "ptrs, with", len(p), "bytes remaining")
   172  		panic("gcprog: extra data at end of program")
   173  	}
   174  	return n
   175  }
   176  
   177  // readvarint reads a varint from p, returning the value and the remainder of p.
   178  func readvarint(p []byte) (int64, []byte) {
   179  	var v int64
   180  	var nb uint
   181  	for {
   182  		c := p[0]
   183  		p = p[1:]
   184  		v |= int64(c&^0x80) << nb
   185  		nb += 7
   186  		if c&0x80 == 0 {
   187  			break
   188  		}
   189  	}
   190  	return v, p
   191  }
   192  
   193  // lit adds a single literal bit to w.
   194  func (w *Writer) lit(x byte) {
   195  	if w.nb == progMaxLiteral {
   196  		w.flushlit()
   197  	}
   198  	w.b[w.nb] = x
   199  	w.nb++
   200  	w.index++
   201  }
   202  
   203  // varint emits the varint encoding of x.
   204  func (w *Writer) varint(x int64) {
   205  	if x < 0 {
   206  		panic("gcprog: negative varint")
   207  	}
   208  	for x >= 0x80 {
   209  		w.byte(byte(0x80 | x))
   210  		x >>= 7
   211  	}
   212  	w.byte(byte(x))
   213  }
   214  
   215  // flushlit flushes any pending literal bits.
   216  func (w *Writer) flushlit() {
   217  	if w.nb == 0 {
   218  		return
   219  	}
   220  	if w.debug != nil {
   221  		fmt.Fprintf(w.debug, "gcprog: flush %d literals\n", w.nb)
   222  		fmt.Fprintf(w.debug, "\t%v\n", w.b[:w.nb])
   223  		fmt.Fprintf(w.debug, "\t%02x", byte(w.nb))
   224  	}
   225  	w.byte(byte(w.nb))
   226  	var bits uint8
   227  	for i := 0; i < w.nb; i++ {
   228  		bits |= w.b[i] << uint(i%8)
   229  		if (i+1)%8 == 0 {
   230  			if w.debug != nil {
   231  				fmt.Fprintf(w.debug, " %02x", bits)
   232  			}
   233  			w.byte(bits)
   234  			bits = 0
   235  		}
   236  	}
   237  	if w.nb%8 != 0 {
   238  		if w.debug != nil {
   239  			fmt.Fprintf(w.debug, " %02x", bits)
   240  		}
   241  		w.byte(bits)
   242  	}
   243  	if w.debug != nil {
   244  		fmt.Fprintf(w.debug, "\n")
   245  	}
   246  	w.nb = 0
   247  }
   248
View as plain text