Hex Artifact Content

Artifact 4f6ff0f55aacba239c9da948195392852f8cd91a:


0000: 2f 2f 20 50 61 63 6b 61 67 65 20 70 72 65 64 69  // Package predi
0010: 63 74 6f 72 20 69 6d 70 6c 65 6d 65 6e 74 73 20  ctor implements 
0020: 74 68 65 20 70 72 65 64 69 63 74 6f 72 20 63 6f  the predictor co
0030: 6d 70 72 65 73 73 69 6f 6e 2f 64 65 63 6f 6d 70  mpression/decomp
0040: 72 65 73 73 69 6f 6e 20 61 6c 67 6f 72 69 74 68  ression algorith
0050: 6d 0a 2f 2f 20 61 73 20 73 70 65 63 69 66 69 65  m.// as specifie
0060: 64 20 62 79 20 52 46 43 31 39 37 38 20 2d 20 50  d by RFC1978 - P
0070: 50 50 20 50 72 65 64 69 63 74 6f 72 20 43 6f 6d  PP Predictor Com
0080: 70 72 65 73 73 69 6f 6e 20 50 72 6f 74 6f 63 6f  pression Protoco
0090: 6c 0a 70 61 63 6b 61 67 65 20 70 72 65 64 69 63  l.package predic
00a0: 74 6f 72 0a 0a 69 6d 70 6f 72 74 20 28 0a 09 62  tor..import (..b
00b0: 69 74 73 20 22 30 64 65 76 2e 6f 72 67 2f 62 69  its "0dev.org/bi
00c0: 74 73 22 0a 09 69 6f 75 20 22 30 64 65 76 2e 6f  ts"..iou "0dev.o
00d0: 72 67 2f 69 6f 75 74 69 6c 22 0a 09 22 69 6f 22  rg/ioutil".."io"
00e0: 0a 29 0a 0a 2f 2f 20 54 68 65 20 63 6f 6e 74 65  .)..// The conte
00f0: 78 74 20 73 74 72 75 63 74 20 63 6f 6e 74 61 69  xt struct contai
0100: 6e 73 20 74 68 65 20 70 72 65 64 69 63 74 6f 72  ns the predictor
0110: 27 73 20 61 6c 67 6f 72 69 74 68 6d 20 67 75 65  's algorithm gue
0120: 73 73 20 74 61 62 6c 65 0a 2f 2f 20 61 6e 64 20  ss table.// and 
0130: 74 68 65 20 63 75 72 72 65 6e 74 20 76 61 6c 75  the current valu
0140: 65 20 6f 66 20 69 74 73 20 69 6e 70 75 74 2f 6f  e of its input/o
0150: 75 74 70 75 74 20 68 61 73 68 0a 74 79 70 65 20  utput hash.type 
0160: 63 6f 6e 74 65 78 74 20 73 74 72 75 63 74 20 7b  context struct {
0170: 0a 09 74 61 62 6c 65 20 5b 31 20 3c 3c 20 31 36  ..table [1 << 16
0180: 5d 62 79 74 65 0a 09 68 61 73 68 20 20 75 69 6e  ]byte..hash  uin
0190: 74 31 36 0a 7d 0a 0a 2f 2f 20 54 68 65 20 66 6f  t16.}..// The fo
01a0: 6c 6c 6f 77 69 6e 67 20 68 61 73 68 20 63 6f 64  llowing hash cod
01b0: 65 20 69 73 20 74 68 65 20 68 65 61 72 74 20 6f  e is the heart o
01c0: 66 20 74 68 65 20 61 6c 67 6f 72 69 74 68 6d 3a  f the algorithm:
01d0: 0a 2f 2f 20 49 74 20 62 75 69 6c 64 73 20 61 20  .// It builds a 
01e0: 73 6c 69 64 69 6e 67 20 68 61 73 68 20 73 75 6d  sliding hash sum
01f0: 20 6f 66 20 74 68 65 20 70 72 65 76 69 6f 75 73   of the previous
0200: 20 33 2d 61 6e 64 2d 61 2d 62 69 74 0a 2f 2f 20   3-and-a-bit.// 
0210: 63 68 61 72 61 63 74 65 72 73 20 77 68 69 63 68  characters which
0220: 20 77 69 6c 6c 20 62 65 20 75 73 65 64 20 74 6f   will be used to
0230: 20 69 6e 64 65 78 20 74 68 65 20 67 75 65 73 73   index the guess
0240: 20 74 61 62 6c 65 2e 0a 2f 2f 20 41 20 62 65 74   table..// A bet
0250: 74 65 72 20 68 61 73 68 20 66 75 6e 63 74 69 6f  ter hash functio
0260: 6e 20 77 6f 75 6c 64 20 72 65 73 75 6c 74 20 69  n would result i
0270: 6e 20 61 64 64 69 74 69 6f 6e 61 6c 20 63 6f 6d  n additional com
0280: 70 72 65 73 73 69 6f 6e 2c 0a 2f 2f 20 61 74 20  pression,.// at 
0290: 74 68 65 20 65 78 70 65 6e 73 65 20 6f 66 20 74  the expense of t
02a0: 69 6d 65 2e 0a 66 75 6e 63 20 28 63 74 78 20 2a  ime..func (ctx *
02b0: 63 6f 6e 74 65 78 74 29 20 75 70 64 61 74 65 28  context) update(
02c0: 76 61 6c 20 62 79 74 65 29 20 7b 0a 09 63 74 78  val byte) {..ctx
02d0: 2e 68 61 73 68 20 3d 20 28 63 74 78 2e 68 61 73  .hash = (ctx.has
02e0: 68 20 3c 3c 20 34 29 20 5e 20 75 69 6e 74 31 36  h << 4) ^ uint16
02f0: 28 76 61 6c 29 0a 7d 0a 0a 2f 2f 20 52 65 74 75  (val).}..// Retu
0300: 72 6e 73 20 61 6e 20 69 6f 2e 57 72 69 74 65 72  rns an io.Writer
0310: 20 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 20   implementation 
0320: 74 68 61 74 20 77 72 61 70 73 20 74 68 65 20 70  that wraps the p
0330: 72 6f 76 69 64 65 64 20 69 6f 2e 57 72 69 74 65  rovided io.Write
0340: 72 0a 2f 2f 20 61 6e 64 20 63 6f 6d 70 72 65 73  r.// and compres
0350: 73 65 73 20 64 61 74 61 20 61 63 63 6f 72 64 69  ses data accordi
0360: 6e 67 20 74 6f 20 74 68 65 20 70 72 65 64 69 63  ng to the predic
0370: 74 6f 72 20 61 6c 67 6f 72 69 74 68 6d 0a 2f 2f  tor algorithm.//
0380: 0a 2f 2f 20 49 74 20 63 61 6e 20 62 75 66 66 65  .// It can buffe
0390: 72 20 64 61 74 61 20 61 73 20 74 68 65 20 70 72  r data as the pr
03a0: 65 64 69 63 74 6f 72 20 6d 61 6e 64 61 74 65 73  edictor mandates
03b0: 20 38 2d 62 79 74 65 20 62 6c 6f 63 6b 73 20 77   8-byte blocks w
03c0: 69 74 68 20 61 20 68 65 61 64 65 72 2e 0a 2f 2f  ith a header..//
03d0: 20 41 20 63 61 6c 6c 20 77 69 74 68 20 6e 6f 20   A call with no 
03e0: 64 61 74 61 20 77 69 6c 6c 20 66 6f 72 63 65 20  data will force 
03f0: 61 20 66 6c 75 73 68 2e 0a 66 75 6e 63 20 43 6f  a flush..func Co
0400: 6d 70 72 65 73 73 6f 72 28 77 72 69 74 65 72 20  mpressor(writer 
0410: 69 6f 2e 57 72 69 74 65 72 29 20 69 6f 2e 57 72  io.Writer) io.Wr
0420: 69 74 65 72 20 7b 0a 09 76 61 72 20 63 6d 70 20  iter {..var cmp 
0430: 63 6f 6d 70 72 65 73 73 6f 72 0a 09 63 6d 70 2e  compressor..cmp.
0440: 74 61 72 67 65 74 20 3d 20 77 72 69 74 65 72 0a  target = writer.
0450: 09 72 65 74 75 72 6e 20 69 6f 75 2e 53 69 7a 65  .return iou.Size
0460: 64 57 72 69 74 65 72 28 26 63 6d 70 2c 20 38 29  dWriter(&cmp, 8)
0470: 0a 7d 0a 0a 74 79 70 65 20 63 6f 6d 70 72 65 73  .}..type compres
0480: 73 6f 72 20 73 74 72 75 63 74 20 7b 0a 09 63 6f  sor struct {..co
0490: 6e 74 65 78 74 0a 09 74 61 72 67 65 74 20 69 6f  ntext..target io
04a0: 2e 57 72 69 74 65 72 0a 7d 0a 0a 2f 2f 20 4e 6f  .Writer.}..// No
04b0: 74 65 3a 20 74 68 69 73 20 6d 65 74 68 6f 64 20  te: this method 
04c0: 64 6f 65 73 20 6e 6f 74 20 69 6d 70 6c 65 6d 65  does not impleme
04d0: 6e 74 20 74 68 65 20 66 75 6c 6c 20 69 6f 2e 57  nt the full io.W
04e0: 72 69 74 65 72 27 73 20 57 72 69 74 65 28 29 20  riter's Write() 
04f0: 73 65 6d 61 6e 74 69 63 73 0a 66 75 6e 63 20 28  semantics.func (
0500: 63 74 78 20 2a 63 6f 6d 70 72 65 73 73 6f 72 29  ctx *compressor)
0510: 20 57 72 69 74 65 28 64 61 74 61 20 5b 5d 62 79   Write(data []by
0520: 74 65 29 20 28 69 6e 74 2c 20 65 72 72 6f 72 29  te) (int, error)
0530: 20 7b 0a 09 76 61 72 20 28 0a 09 09 62 6c 6f 63   {..var (...bloc
0540: 6b 53 69 7a 65 20 20 69 6e 74 20 3d 20 38 0a 09  kSize  int = 8..
0550: 09 64 61 74 61 6c 65 6e 67 74 68 20 69 6e 74 20  .datalength int 
0560: 3d 20 6c 65 6e 28 64 61 74 61 29 0a 09 29 0a 0a  = len(data)..)..
0570: 09 69 66 20 64 61 74 61 6c 65 6e 67 74 68 20 3d  .if datalength =
0580: 3d 20 30 20 7b 0a 09 09 72 65 74 75 72 6e 20 30  = 0 {...return 0
0590: 2c 20 6e 69 6c 0a 09 7d 0a 0a 09 69 66 20 64 61  , nil..}...if da
05a0: 74 61 6c 65 6e 67 74 68 20 3c 20 62 6c 6f 63 6b  talength < block
05b0: 53 69 7a 65 20 7b 0a 09 09 62 6c 6f 63 6b 53 69  Size {...blockSi
05c0: 7a 65 20 3d 20 64 61 74 61 6c 65 6e 67 74 68 0a  ze = datalength.
05d0: 09 7d 0a 0a 09 76 61 72 20 62 75 66 20 5b 5d 62  .}...var buf []b
05e0: 79 74 65 20 3d 20 6d 61 6b 65 28 5b 5d 62 79 74  yte = make([]byt
05f0: 65 2c 20 31 2c 20 62 6c 6f 63 6b 53 69 7a 65 2b  e, 1, blockSize+
0600: 31 29 0a 09 66 6f 72 20 62 6c 6f 63 6b 20 3a 3d  1)..for block :=
0610: 20 30 3b 20 62 6c 6f 63 6b 20 3c 20 64 61 74 61   0; block < data
0620: 6c 65 6e 67 74 68 2f 62 6c 6f 63 6b 53 69 7a 65  length/blockSize
0630: 3b 20 62 6c 6f 63 6b 2b 2b 20 7b 0a 09 09 66 6f  ; block++ {...fo
0640: 72 20 69 20 3a 3d 20 30 3b 20 69 20 3c 20 62 6c  r i := 0; i < bl
0650: 6f 63 6b 53 69 7a 65 3b 20 69 2b 2b 20 7b 0a 09  ockSize; i++ {..
0660: 09 09 76 61 72 20 63 75 72 72 65 6e 74 20 62 79  ..var current by
0670: 74 65 20 3d 20 64 61 74 61 5b 28 62 6c 6f 63 6b  te = data[(block
0680: 2a 62 6c 6f 63 6b 53 69 7a 65 29 2b 69 5d 0a 09  *blockSize)+i]..
0690: 09 09 69 66 20 63 74 78 2e 74 61 62 6c 65 5b 63  ..if ctx.table[c
06a0: 74 78 2e 68 61 73 68 5d 20 3d 3d 20 63 75 72 72  tx.hash] == curr
06b0: 65 6e 74 20 7b 0a 09 09 09 09 2f 2f 20 47 75 65  ent {.....// Gue
06c0: 73 73 20 77 61 73 20 72 69 67 68 74 20 2d 20 64  ss was right - d
06d0: 6f 6e 27 74 20 6f 75 74 70 75 74 0a 09 09 09 09  on't output.....
06e0: 62 75 66 5b 30 5d 20 7c 3d 20 31 20 3c 3c 20 75  buf[0] |= 1 << u
06f0: 69 6e 74 28 69 29 0a 09 09 09 7d 20 65 6c 73 65  int(i)....} else
0700: 20 7b 0a 09 09 09 09 2f 2f 20 47 75 65 73 73 20   {.....// Guess 
0710: 77 61 73 20 77 72 6f 6e 67 2c 20 6f 75 74 70 75  was wrong, outpu
0720: 74 20 63 68 61 72 0a 09 09 09 09 63 74 78 2e 74  t char.....ctx.t
0730: 61 62 6c 65 5b 63 74 78 2e 68 61 73 68 5d 20 3d  able[ctx.hash] =
0740: 20 63 75 72 72 65 6e 74 0a 09 09 09 09 62 75 66   current.....buf
0750: 20 3d 20 61 70 70 65 6e 64 28 62 75 66 2c 20 63   = append(buf, c
0760: 75 72 72 65 6e 74 29 0a 09 09 09 7d 0a 09 09 09  urrent)....}....
0770: 63 74 78 2e 75 70 64 61 74 65 28 63 75 72 72 65  ctx.update(curre
0780: 6e 74 29 0a 09 09 7d 0a 0a 09 09 69 66 20 63 2c  nt)...}....if c,
0790: 20 65 72 72 20 3a 3d 20 63 74 78 2e 74 61 72 67   err := ctx.targ
07a0: 65 74 2e 57 72 69 74 65 28 62 75 66 29 3b 20 65  et.Write(buf); e
07b0: 72 72 20 21 3d 20 6e 69 6c 20 7b 0a 09 09 09 72  rr != nil {....r
07c0: 65 74 75 72 6e 20 28 62 6c 6f 63 6b 20 2a 20 62  eturn (block * b
07d0: 6c 6f 63 6b 53 69 7a 65 29 20 2b 20 63 2c 20 65  lockSize) + c, e
07e0: 72 72 0a 09 09 7d 0a 0a 09 09 2f 2f 20 52 65 73  rr...}....// Res
07f0: 65 74 20 74 68 65 20 66 6c 61 67 73 20 61 6e 64  et the flags and
0800: 20 62 75 66 66 65 72 20 66 6f 72 20 74 68 65 20   buffer for the 
0810: 6e 65 78 74 20 69 74 65 72 61 74 69 6f 6e 0a 09  next iteration..
0820: 09 62 75 66 2c 20 62 75 66 5b 30 5d 20 3d 20 62  .buf, buf[0] = b
0830: 75 66 5b 3a 31 5d 2c 20 30 0a 09 7d 0a 0a 09 72  uf[:1], 0..}...r
0840: 65 74 75 72 6e 20 64 61 74 61 6c 65 6e 67 74 68  eturn datalength
0850: 2c 20 6e 69 6c 0a 7d 0a 0a 2f 2f 20 52 65 74 75  , nil.}..// Retu
0860: 72 6e 73 20 61 6e 20 69 6f 2e 52 65 61 64 65 72  rns an io.Reader
0870: 20 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 20   implementation 
0880: 74 68 61 74 20 77 72 61 70 73 20 74 68 65 20 70  that wraps the p
0890: 72 6f 76 69 64 65 64 20 69 6f 2e 52 65 61 64 65  rovided io.Reade
08a0: 72 0a 2f 2f 20 61 6e 64 20 64 65 63 6f 6d 70 72  r.// and decompr
08b0: 65 73 73 65 73 20 64 61 74 61 20 61 63 63 6f 72  esses data accor
08c0: 64 69 6e 67 20 74 6f 20 74 68 65 20 70 72 65 64  ding to the pred
08d0: 69 63 74 6f 72 20 61 6c 67 6f 72 69 74 68 6d 0a  ictor algorithm.
08e0: 66 75 6e 63 20 44 65 63 6f 6d 70 72 65 73 73 6f  func Decompresso
08f0: 72 28 72 65 61 64 65 72 20 69 6f 2e 52 65 61 64  r(reader io.Read
0900: 65 72 29 20 69 6f 2e 52 65 61 64 65 72 20 7b 0a  er) io.Reader {.
0910: 09 76 61 72 20 64 63 6d 70 20 64 65 63 6f 6d 70  .var dcmp decomp
0920: 72 65 73 73 6f 72 0a 09 64 63 6d 70 2e 73 6f 75  ressor..dcmp.sou
0930: 72 63 65 20 3d 20 72 65 61 64 65 72 0a 09 72 65  rce = reader..re
0940: 74 75 72 6e 20 69 6f 75 2e 53 69 7a 65 64 52 65  turn iou.SizedRe
0950: 61 64 65 72 28 26 64 63 6d 70 2c 20 38 29 0a 7d  ader(&dcmp, 8).}
0960: 0a 0a 74 79 70 65 20 64 65 63 6f 6d 70 72 65 73  ..type decompres
0970: 73 6f 72 20 73 74 72 75 63 74 20 7b 0a 09 63 6f  sor struct {..co
0980: 6e 74 65 78 74 0a 09 73 6f 75 72 63 65 20 69 6f  ntext..source io
0990: 2e 52 65 61 64 65 72 0a 7d 0a 0a 2f 2f 20 4e 6f  .Reader.}..// No
09a0: 74 65 3a 20 74 68 69 73 20 6d 65 74 68 6f 64 20  te: this method 
09b0: 64 6f 65 73 20 6e 6f 74 20 69 6d 70 6c 65 6d 65  does not impleme
09c0: 6e 74 20 74 68 65 20 66 75 6c 6c 20 69 6f 2e 52  nt the full io.R
09d0: 65 61 64 65 72 27 73 20 52 65 61 64 28 29 20 73  eader's Read() s
09e0: 65 6d 61 6e 74 69 63 73 0a 66 75 6e 63 20 28 63  emantics.func (c
09f0: 74 78 20 2a 64 65 63 6f 6d 70 72 65 73 73 6f 72  tx *decompressor
0a00: 29 20 52 65 61 64 28 6f 75 74 70 75 74 20 5b 5d  ) Read(output []
0a10: 62 79 74 65 29 20 28 69 6e 74 2c 20 65 72 72 6f  byte) (int, erro
0a20: 72 29 20 7b 0a 09 76 61 72 20 28 0a 09 09 65 72  r) {..var (...er
0a30: 72 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  r               
0a40: 20 20 20 20 20 20 20 20 20 20 20 65 72 72 6f 72             error
0a50: 0a 09 09 62 75 66 66 65 72 20 20 20 20 20 20 20  ...buffer       
0a60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0a70: 5b 5d 62 79 74 65 20 3d 20 6d 61 6b 65 28 5b 5d  []byte = make([]
0a80: 62 79 74 65 2c 20 38 29 0a 09 09 66 6c 61 67 73  byte, 8)...flags
0a90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0aa0: 20 20 20 20 20 20 20 20 62 79 74 65 0a 09 09 70          byte...p
0ab0: 72 65 64 69 63 74 65 64 2c 20 72 63 2c 20 74 6f  redicted, rc, to
0ac0: 74 61 6c 2c 20 63 6f 70 69 65 64 20 69 6e 74 0a  tal, copied int.
0ad0: 09 29 0a 0a 09 2f 2f 20 52 65 61 64 20 74 68 65  .)...// Read the
0ae0: 20 6e 65 78 74 20 70 72 65 64 69 63 74 69 6f 6e   next prediction
0af0: 20 68 65 61 64 65 72 0a 72 65 61 64 48 65 61 64   header.readHead
0b00: 65 72 3a 0a 09 72 63 2c 20 65 72 72 20 3d 20 63  er:..rc, err = c
0b10: 74 78 2e 73 6f 75 72 63 65 2e 52 65 61 64 28 62  tx.source.Read(b
0b20: 75 66 66 65 72 5b 3a 31 5d 29 0a 09 2f 2f 20 46  uffer[:1])..// F
0b30: 61 69 6c 20 6f 6e 20 65 72 72 6f 72 20 75 6e 6c  ail on error unl
0b40: 65 73 73 20 69 74 20 69 73 20 45 4f 46 0a 09 69  ess it is EOF..i
0b50: 66 20 65 72 72 20 21 3d 20 6e 69 6c 20 26 26 20  f err != nil && 
0b60: 65 72 72 20 21 3d 20 69 6f 2e 45 4f 46 20 7b 0a  err != io.EOF {.
0b70: 09 09 72 65 74 75 72 6e 20 74 6f 74 61 6c 2c 20  ..return total, 
0b80: 65 72 72 0a 09 7d 20 65 6c 73 65 20 69 66 20 72  err..} else if r
0b90: 63 20 3d 3d 20 30 20 7b 0a 09 09 72 65 74 75 72  c == 0 {...retur
0ba0: 6e 20 74 6f 74 61 6c 2c 20 65 72 72 0a 09 7d 0a  n total, err..}.
0bb0: 0a 09 2f 2f 20 43 6f 70 79 20 74 68 65 20 70 72  ..// Copy the pr
0bc0: 65 64 69 63 74 69 6f 6e 20 68 65 61 64 65 72 20  ediction header 
0bd0: 61 6e 64 20 63 61 6c 63 75 6c 61 74 65 20 74 68  and calculate th
0be0: 65 20 6e 75 6d 62 65 72 20 6f 66 20 73 75 62 73  e number of subs
0bf0: 65 71 75 65 6e 74 20 62 79 74 65 73 20 74 6f 20  equent bytes to 
0c00: 72 65 61 64 0a 09 66 6c 61 67 73 20 3d 20 62 75  read..flags = bu
0c10: 66 66 65 72 5b 30 5d 0a 09 70 72 65 64 69 63 74  ffer[0]..predict
0c20: 65 64 20 3d 20 62 69 74 73 2e 48 61 6d 6d 69 6e  ed = bits.Hammin
0c30: 67 28 66 6c 61 67 73 29 0a 0a 09 2f 2f 20 52 65  g(flags)...// Re
0c40: 61 64 20 74 68 65 20 6e 6f 6e 2d 70 72 65 64 69  ad the non-predi
0c50: 63 74 65 64 20 62 79 74 65 73 20 61 6e 64 20 70  cted bytes and p
0c60: 6c 61 63 65 20 74 68 65 6d 20 69 6e 20 74 68 65  lace them in the
0c70: 20 65 6e 64 20 6f 66 20 74 68 65 20 62 75 66 66   end of the buff
0c80: 65 72 0a 09 72 63 2c 20 65 72 72 20 3d 20 63 74  er..rc, err = ct
0c90: 78 2e 73 6f 75 72 63 65 2e 52 65 61 64 28 62 75  x.source.Read(bu
0ca0: 66 66 65 72 5b 70 72 65 64 69 63 74 65 64 3a 5d  ffer[predicted:]
0cb0: 29 0a 72 65 74 72 79 44 61 74 61 3a 0a 09 69 66  ).retryData:..if
0cc0: 20 28 72 63 20 3c 20 28 38 20 2d 20 70 72 65 64   (rc < (8 - pred
0cd0: 69 63 74 65 64 29 29 20 26 26 20 65 72 72 20 3d  icted)) && err =
0ce0: 3d 20 6e 69 6c 20 7b 0a 09 09 2f 2f 20 52 65 74  = nil {...// Ret
0cf0: 72 79 20 74 68 65 20 72 65 61 64 20 69 66 20 77  ry the read if w
0d00: 65 20 68 61 76 65 20 66 65 77 65 72 20 62 79 74  e have fewer byt
0d10: 65 73 20 74 68 61 6e 20 77 68 61 74 20 74 68 65  es than what the
0d20: 20 70 72 65 64 69 63 74 69 6f 6e 20 68 65 61 64   prediction head
0d30: 65 72 20 69 6e 64 69 63 61 74 65 73 0a 09 09 76  er indicates...v
0d40: 61 72 20 72 20 69 6e 74 0a 09 09 72 2c 20 65 72  ar r int...r, er
0d50: 72 20 3d 20 63 74 78 2e 73 6f 75 72 63 65 2e 52  r = ctx.source.R
0d60: 65 61 64 28 62 75 66 66 65 72 5b 70 72 65 64 69  ead(buffer[predi
0d70: 63 74 65 64 2b 72 63 3a 5d 29 0a 09 09 72 63 20  cted+rc:])...rc 
0d80: 2b 3d 20 72 0a 09 09 67 6f 74 6f 20 72 65 74 72  += r...goto retr
0d90: 79 44 61 74 61 0a 09 7d 20 2f 2f 20 43 6f 6e 74  yData..} // Cont
0da0: 69 6e 75 65 20 6f 6e 20 61 6e 79 20 65 72 72 6f  inue on any erro
0db0: 72 2c 20 74 72 79 20 74 6f 20 64 65 63 6f 6d 70  r, try to decomp
0dc0: 72 65 73 73 20 61 6e 64 20 72 65 74 75 72 6e 20  ress and return 
0dd0: 69 74 20 61 6c 6f 6e 67 20 74 68 65 20 72 65 73  it along the res
0de0: 75 6c 74 0a 0a 09 2f 2f 20 72 63 20 6e 6f 77 20  ult...// rc now 
0df0: 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 61 6d 6f  contains the amo
0e00: 75 6e 74 20 6f 66 20 61 63 74 75 61 6c 20 62 79  unt of actual by
0e10: 74 65 73 20 69 6e 20 74 68 69 73 20 63 79 63 6c  tes in this cycl
0e20: 65 20 28 75 73 75 61 6c 6c 79 20 38 29 0a 09 72  e (usually 8)..r
0e30: 63 20 2b 3d 20 70 72 65 64 69 63 74 65 64 0a 0a  c += predicted..
0e40: 09 2f 2f 20 57 61 6c 6b 20 74 68 65 20 62 75 66  .// Walk the buf
0e50: 66 65 72 2c 20 66 69 6c 6c 69 6e 67 20 69 6e 20  fer, filling in 
0e60: 74 68 65 20 70 72 65 64 69 63 74 65 64 20 62 6c  the predicted bl
0e70: 61 6e 6b 73 2c 0a 09 2f 2f 20 72 65 6c 6f 63 61  anks,..// reloca
0e80: 74 69 6e 67 20 72 65 61 64 20 62 79 74 65 73 20  ting read bytes 
0e90: 61 6e 64 20 61 6e 64 20 75 70 64 61 74 69 6e 67  and and updating
0ea0: 20 74 68 65 20 67 75 65 73 73 20 74 61 62 6c 65   the guess table
0eb0: 0a 09 66 6f 72 20 69 2c 20 61 20 3a 3d 20 30 2c  ..for i, a := 0,
0ec0: 20 70 72 65 64 69 63 74 65 64 3b 20 69 20 3c 20   predicted; i < 
0ed0: 72 63 3b 20 69 2b 2b 20 7b 0a 09 09 69 66 20 28  rc; i++ {...if (
0ee0: 66 6c 61 67 73 20 26 20 28 31 20 3c 3c 20 75 69  flags & (1 << ui
0ef0: 6e 74 28 69 29 29 29 20 3e 20 30 20 7b 0a 09 09  nt(i))) > 0 {...
0f00: 09 2f 2f 20 47 75 65 73 73 20 73 75 63 63 65 65  .// Guess succee
0f10: 64 65 64 2c 20 66 69 6c 6c 20 69 6e 20 66 72 6f  ded, fill in fro
0f20: 6d 20 74 68 65 20 74 61 62 6c 65 0a 09 09 09 62  m the table....b
0f30: 75 66 66 65 72 5b 69 5d 20 3d 20 63 74 78 2e 74  uffer[i] = ctx.t
0f40: 61 62 6c 65 5b 63 74 78 2e 68 61 73 68 5d 0a 09  able[ctx.hash]..
0f50: 09 7d 20 65 6c 73 65 20 7b 0a 09 09 09 2f 2f 20  .} else {....// 
0f60: 52 65 6c 6f 63 61 74 65 20 61 20 72 65 61 64 20  Relocate a read 
0f70: 62 79 74 65 20 61 6e 64 20 61 64 76 61 6e 63 65  byte and advance
0f80: 20 74 68 65 20 72 65 61 64 20 62 79 74 65 20 69   the read byte i
0f90: 6e 64 65 78 0a 09 09 09 62 75 66 66 65 72 5b 69  ndex....buffer[i
0fa0: 5d 2c 20 61 20 3d 20 62 75 66 66 65 72 5b 61 5d  ], a = buffer[a]
0fb0: 2c 20 61 2b 31 0a 09 09 09 2f 2f 20 47 75 65 73  , a+1....// Gues
0fc0: 73 20 66 61 69 6c 65 64 2c 20 75 70 64 61 74 65  s failed, update
0fd0: 20 74 68 65 20 74 61 62 6c 65 0a 09 09 09 63 74   the table....ct
0fe0: 78 2e 74 61 62 6c 65 5b 63 74 78 2e 68 61 73 68  x.table[ctx.hash
0ff0: 5d 20 3d 20 62 75 66 66 65 72 5b 69 5d 0a 09 09  ] = buffer[i]...
1000: 7d 0a 09 09 2f 2f 20 55 70 64 61 74 65 20 74 68  }...// Update th
1010: 65 20 68 61 73 68 0a 09 09 63 74 78 2e 75 70 64  e hash...ctx.upd
1020: 61 74 65 28 62 75 66 66 65 72 5b 69 5d 29 0a 09  ate(buffer[i])..
1030: 7d 0a 0a 09 2f 2f 20 43 6f 70 79 20 74 68 65 20  }...// Copy the 
1040: 64 65 63 6f 6d 70 72 65 73 73 65 64 20 64 61 74  decompressed dat
1050: 61 20 74 6f 20 74 68 65 20 6f 75 74 70 75 74 20  a to the output 
1060: 61 6e 64 20 61 63 63 75 6d 75 6c 61 74 65 20 74  and accumulate t
1070: 68 65 20 63 6f 75 6e 74 0a 09 63 6f 70 69 65 64  he count..copied
1080: 20 3d 20 63 6f 70 79 28 6f 75 74 70 75 74 2c 20   = copy(output, 
1090: 62 75 66 66 65 72 5b 3a 72 63 5d 29 0a 09 74 6f  buffer[:rc])..to
10a0: 74 61 6c 20 2b 3d 20 63 6f 70 69 65 64 0a 0a 09  tal += copied...
10b0: 2f 2f 20 4c 6f 6f 70 20 66 6f 72 20 61 6e 6f 74  // Loop for anot
10c0: 68 65 72 20 70 61 73 73 20 69 66 20 74 68 65 72  her pass if ther
10d0: 65 20 69 73 20 61 76 61 69 6c 61 62 6c 65 20 73  e is available s
10e0: 70 61 63 65 20 69 6e 20 74 68 65 20 6f 75 74 70  pace in the outp
10f0: 75 74 0a 09 6f 75 74 70 75 74 20 3d 20 6f 75 74  ut..output = out
1100: 70 75 74 5b 63 6f 70 69 65 64 3a 5d 0a 09 69 66  put[copied:]..if
1110: 20 6c 65 6e 28 6f 75 74 70 75 74 29 20 3e 20 30   len(output) > 0
1120: 20 26 26 20 65 72 72 20 3d 3d 20 6e 69 6c 20 7b   && err == nil {
1130: 0a 09 09 67 6f 74 6f 20 72 65 61 64 48 65 61 64  ...goto readHead
1140: 65 72 0a 09 7d 0a 0a 09 72 65 74 75 72 6e 20 74  er..}...return t
1150: 6f 74 61 6c 2c 20 65 72 72 0a 7d 0a              otal, err.}.