Check-in [f06f8cd058]
Overview
SHA1:f06f8cd058563e2a8fd404c3d1578857f83a14df
Date: 2014-12-25 08:48:58
User: spaskalev
Comment:Allocate the predictor's decompression buffer per Read call.
Timelines: family | ancestors | descendants | both | trunk
Downloads: Tarball | ZIP archive
Other Links: files | file ages | folders | manifest
Tags And Properties
Context
2014-12-26
15:50
[ad5c25d9ab] Initial implementation of package mtf - a move-to-front transform. (user: spaskalev, tags: trunk)
2014-12-25
08:48
[f06f8cd058] Allocate the predictor's decompression buffer per Read call. (user: spaskalev, tags: trunk)
01:25
[2b1ed8e45e] Removed pdc's output buffer when decompressing as io.Copy uses a sufficiently-large buffer internally. (user: spaskalev, tags: trunk)
Changes

Modified src/0dev.org/bits/bits.go from [7a154cae58] to [16bc764710].

     1      1   // Package bits provides various constructs that work with bits
     2      2   package bits
     3      3   
     4      4   import (
     5      5   	"strconv"
     6      6   )
     7      7   
     8         -var hamming = [256]byte{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
            8  +var hamming = [256]int{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
     9      9   	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    10     10   	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    11     11   	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    12     12   	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    13     13   	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    14     14   	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    15     15   	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
................................................................................
    20     20   	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    21     21   	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    22     22   	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    23     23   	4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
    24     24   }
    25     25   
    26     26   // Returns the number of raised bits in the given byte
    27         -func Hamming(b byte) byte {
           27  +func Hamming(b byte) int {
    28     28   	return hamming[b]
    29     29   }
    30     30   
    31     31   var reversed = [256]byte{
    32     32   	0, 128, 64, 192, 32, 160, 96, 224, 16, 144, 80, 208, 48, 176, 112, 240,
    33     33   	8, 136, 72, 200, 40, 168, 104, 232, 24, 152, 88, 216, 56, 184, 120, 248,
    34     34   	4, 132, 68, 196, 36, 164, 100, 228, 20, 148, 84, 212, 52, 180, 116, 244,

Modified src/0dev.org/bits/bits_test.go from [255f42be62] to [ed7ac493ff].

     3      3   import (
     4      4   	"strconv"
     5      5   	"testing"
     6      6   )
     7      7   
     8      8   func TestHamming(t *testing.T) {
     9      9   	for i := 0; i < 256; i++ {
    10         -		b, result := i, byte(0)
           10  +		b, result := i, 0
    11     11   		for b > 0 {
    12     12   			if (b & 1) > 0 {
    13     13   				result++
    14     14   			}
    15     15   			b = b >> 1
    16     16   		}
    17     17   		if result != Hamming(byte(i)) {

Modified src/0dev.org/predictor/predictor.go from [3161320c11] to [4f6ff0f55a].

    82     82   }
    83     83   
    84     84   // Returns an io.Reader implementation that wraps the provided io.Reader
    85     85   // and decompresses data according to the predictor algorithm
    86     86   func Decompressor(reader io.Reader) io.Reader {
    87     87   	var dcmp decompressor
    88     88   	dcmp.source = reader
    89         -	dcmp.input = make([]byte, 8)
    90     89   	return iou.SizedReader(&dcmp, 8)
    91     90   }
    92     91   
    93     92   type decompressor struct {
    94     93   	context
    95     94   	source io.Reader
    96         -	input  []byte
    97     95   }
    98     96   
    99     97   // Note: this method does not implement the full io.Reader's Read() semantics
   100     98   func (ctx *decompressor) Read(output []byte) (int, error) {
   101     99   	var (
   102         -		err               error
   103         -		flags, predicted  byte
   104         -		rc, total, copied int
          100  +		err                          error
          101  +		buffer                       []byte = make([]byte, 8)
          102  +		flags                        byte
          103  +		predicted, rc, total, copied int
   105    104   	)
   106    105   
   107    106   	// Read the next prediction header
   108    107   readHeader:
   109         -	rc, err = ctx.source.Read(ctx.input[:1])
          108  +	rc, err = ctx.source.Read(buffer[:1])
   110    109   	// Fail on error unless it is EOF
   111    110   	if err != nil && err != io.EOF {
   112    111   		return total, err
   113    112   	} else if rc == 0 {
   114    113   		return total, err
   115    114   	}
   116    115   
   117    116   	// Copy the prediction header and calculate the number of subsequent bytes to read
   118         -	flags = ctx.input[0]
          117  +	flags = buffer[0]
   119    118   	predicted = bits.Hamming(flags)
   120    119   
   121    120   	// Read the non-predicted bytes and place them in the end of the buffer
   122         -	rc, err = ctx.source.Read(ctx.input[predicted:])
          121  +	rc, err = ctx.source.Read(buffer[predicted:])
   123    122   retryData:
   124         -	if rc < int(8-predicted) && err == nil {
          123  +	if (rc < (8 - predicted)) && err == nil {
   125    124   		// Retry the read if we have fewer bytes than what the prediction header indicates
   126    125   		var r int
   127         -		r, err = ctx.source.Read(ctx.input[int(predicted)+rc:])
          126  +		r, err = ctx.source.Read(buffer[predicted+rc:])
   128    127   		rc += r
   129    128   		goto retryData
   130    129   	} // Continue on any error, try to decompress and return it along the result
   131    130   
   132    131   	// rc now contains the amount of actual bytes in this cycle (usually 8)
   133         -	rc += int(predicted)
          132  +	rc += predicted
   134    133   
   135    134   	// Walk the buffer, filling in the predicted blanks,
   136    135   	// relocating read bytes and and updating the guess table
   137    136   	for i, a := 0, predicted; i < rc; i++ {
   138    137   		if (flags & (1 << uint(i))) > 0 {
   139    138   			// Guess succeeded, fill in from the table
   140         -			ctx.input[i] = ctx.table[ctx.hash]
          139  +			buffer[i] = ctx.table[ctx.hash]
   141    140   		} else {
   142    141   			// Relocate a read byte and advance the read byte index
   143         -			ctx.input[i], a = ctx.input[a], a+1
          142  +			buffer[i], a = buffer[a], a+1
   144    143   			// Guess failed, update the table
   145         -			ctx.table[ctx.hash] = ctx.input[i]
          144  +			ctx.table[ctx.hash] = buffer[i]
   146    145   		}
   147    146   		// Update the hash
   148         -		ctx.update(ctx.input[i])
          147  +		ctx.update(buffer[i])
   149    148   	}
   150    149   
   151    150   	// Copy the decompressed data to the output and accumulate the count
   152         -	copied = copy(output, ctx.input[:rc])
          151  +	copied = copy(output, buffer[:rc])
   153    152   	total += copied
   154    153   
   155    154   	// Loop for another pass if there is available space in the output
   156    155   	output = output[copied:]
   157    156   	if len(output) > 0 && err == nil {
   158    157   		goto readHeader
   159    158   	}
   160    159   
   161    160   	return total, err
   162    161   }