Source file src/pkg/cmd/internal/gcprog/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