Check-in [89bfe97384]
Overview
Comment:Added documentation for the decompressor
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 89bfe973847c1cc1e9bf81a1d583bbeabd4f444c
User & Date: spaskalev on 2014-12-22 19:52:05
Other Links: manifest | tags
Context
2014-12-23
07:52
Added package ioutil with io.Writer and io.Reader function wrappers check-in: 2bcd5307ea user: spaskalev tags: trunk
2014-12-22
19:52
Added documentation for the decompressor check-in: 89bfe97384 user: spaskalev tags: trunk
19:28
Extracted the predictor's hash function as a method of the context struct. Minor changes to the decompressor's variables. check-in: 9dfd3cb1a2 user: spaskalev tags: trunk
Changes

Modified src/0dev.org/predictor/predictor.go from [a4885df9dd] to [290c8bbbe5].

    14     14   }
    15     15   
    16     16   // The following hash code is the heart of the algorithm:
    17     17   // It builds a sliding hash sum of the previous 3-and-a-bit
    18     18   // characters which will be used to index the guess table.
    19     19   // A better hash function would result in additional compression,
    20     20   // at the expense of time.
    21         -func (ctx *context) update(val uint16) {
    22         -	ctx.hash = (ctx.hash << 4) ^ val
           21  +func (ctx *context) update(val byte) {
           22  +	ctx.hash = (ctx.hash << 4) ^ uint16(val)
    23     23   }
    24     24   
    25     25   type compressor func([]byte) error
    26     26   
    27     27   func (w compressor) Write(data []byte) (int, error) {
    28     28   	return len(data), w(data)
    29     29   }
................................................................................
    90     90   					// Guess was right - don't output
    91     91   					buf[0] |= 1 << uint(i)
    92     92   				} else {
    93     93   					// Guess was wrong, output char
    94     94   					ctx.table[ctx.hash] = current
    95     95   					buf = append(buf, current)
    96     96   				}
    97         -				ctx.update(uint16(current))
           97  +				ctx.update(current)
    98     98   			}
    99     99   
   100    100   			if _, err := writer.Write(buf); err != nil {
   101    101   				return err
   102    102   			}
   103    103   
   104    104   			// Reset the flags and buffer for the next iteration
................................................................................
   146    146   
   147    147   		// Check whether we have leftover data in the buffer
   148    148   		if len(ctx.input) > 0 {
   149    149   			rc = copy(output, ctx.input)
   150    150   
   151    151   			// Check whether we still have leftover data in the buffer :)
   152    152   			if rc < len(ctx.input) {
          153  +				// Shift the remaining bytes at the start of the buffer
          154  +				//  and resize the buffer accordingly
   153    155   				ctx.input = ctx.input[:copy(ctx.input, ctx.input[rc:])]
   154    156   			}
   155    157   			return rc, nil
   156    158   		}
   157    159   
   158    160   		// Read the next prediction header
   159    161   	readHeader:
................................................................................
   188    190   		// Walk the buffer, filling in the predicted blanks,
   189    191   		// relocating read bytes and and updating the guess table
   190    192   		for i, a := 0, predicted; i < rc; i++ {
   191    193   			if (flags & (1 << uint(i))) > 0 {
   192    194   				// Guess succeeded, fill in from the table
   193    195   				ctx.input[i] = ctx.table[ctx.hash]
   194    196   			} else {
   195         -				// Relocate a read byte
          197  +				// Relocate a read byte and advance the read byte index
   196    198   				ctx.input[i], a = ctx.input[a], a+1
   197    199   				// Guess failed, update the table
   198    200   				ctx.table[ctx.hash] = ctx.input[i]
   199    201   			}
   200    202   			// Update the hash
   201         -			ctx.update(uint16(ctx.input[i]))
          203  +			ctx.update(ctx.input[i])
   202    204   		}
   203    205   
   204         -		// Copy the decompressed data to the output
   205         -		ctx.input = ctx.input[:rc]
   206         -		copied = copy(output, ctx.input)
   207         -
          206  +		// Copy the decompressed data to the output and accumulate the count
          207  +		copied = copy(output, ctx.input[:rc])
   208    208   		total += copied
   209    209   
   210    210   		// Check for remaining bytes that dont fit in the output buffer
   211    211   		if copied < rc {
   212         -			ctx.input = ctx.input[:copy(ctx.input, ctx.input[copied:])]
          212  +			// Shift the remaining bytes at the start of the buffer
          213  +			//  and resize the buffer accordingly
          214  +			ctx.input = ctx.input[:copy(ctx.input, ctx.input[copied:rc])]
   213    215   		} else {
   214    216   			// Clear the buffer
   215    217   			ctx.input = ctx.input[:0]
   216    218   
          219  +			// Loop for another pass if there is available space in the output
   217    220   			output = output[copied:]
   218    221   			if len(output) > 0 && err == nil {
   219    222   				goto readHeader
   220    223   			}
   221    224   		}
   222    225   
   223    226   		return total, err
   224    227   	})
   225    228   }