Hex Artifact Content

Artifact c018a462969f2ed743af09376d56b7ce279d64e2:


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 22 69 6f 22 0a 29 0a 0a 74 79 70  ts".."io".)..typ
00d0: 65 20 63 6f 6e 74 65 78 74 20 73 74 72 75 63 74  e context struct
00e0: 20 7b 0a 09 74 61 62 6c 65 20 5b 31 20 3c 3c 20   {..table [1 << 
00f0: 31 36 5d 62 79 74 65 0a 09 69 6e 70 75 74 20 5b  16]byte..input [
0100: 5d 62 79 74 65 0a 09 68 61 73 68 20 20 75 69 6e  ]byte..hash  uin
0110: 74 31 36 0a 7d 0a 0a 74 79 70 65 20 63 6f 6d 70  t16.}..type comp
0120: 72 65 73 73 6f 72 20 66 75 6e 63 28 5b 5d 62 79  ressor func([]by
0130: 74 65 29 20 65 72 72 6f 72 0a 0a 66 75 6e 63 20  te) error..func 
0140: 28 77 20 63 6f 6d 70 72 65 73 73 6f 72 29 20 57  (w compressor) W
0150: 72 69 74 65 28 64 61 74 61 20 5b 5d 62 79 74 65  rite(data []byte
0160: 29 20 28 69 6e 74 2c 20 65 72 72 6f 72 29 20 7b  ) (int, error) {
0170: 0a 09 72 65 74 75 72 6e 20 6c 65 6e 28 64 61 74  ..return len(dat
0180: 61 29 2c 20 77 28 64 61 74 61 29 0a 7d 0a 0a 2f  a), w(data).}../
0190: 2f 20 52 65 74 75 72 6e 73 20 61 6e 20 69 6f 2e  / Returns an io.
01a0: 57 72 69 74 65 72 20 69 6d 70 6c 65 6d 65 6e 74  Writer implement
01b0: 61 74 69 6f 6e 20 74 68 61 74 20 77 72 61 70 73  ation that wraps
01c0: 20 74 68 65 20 70 72 6f 76 69 64 65 64 20 69 6f   the provided io
01d0: 2e 57 72 69 74 65 72 0a 2f 2f 20 61 6e 64 20 63  .Writer.// and c
01e0: 6f 6d 70 72 65 73 73 65 73 20 64 61 74 61 20 61  ompresses data a
01f0: 63 63 6f 72 64 69 6e 67 20 74 6f 20 74 68 65 20  ccording to the 
0200: 70 72 65 64 69 63 74 6f 72 20 61 6c 67 6f 72 69  predictor algori
0210: 74 68 6d 0a 2f 2f 0a 2f 2f 20 49 74 20 63 61 6e  thm.//.// It can
0220: 20 62 75 66 66 65 72 20 64 61 74 61 20 61 73 20   buffer data as 
0230: 74 68 65 20 70 72 65 64 69 63 74 6f 72 20 6d 61  the predictor ma
0240: 6e 64 61 74 65 73 20 38 2d 62 79 74 65 20 62 6c  ndates 8-byte bl
0250: 6f 63 6b 73 20 77 69 74 68 20 61 20 68 65 61 64  ocks with a head
0260: 65 72 2e 0a 2f 2f 20 41 20 63 61 6c 6c 20 77 69  er..// A call wi
0270: 74 68 20 6e 6f 20 64 61 74 61 20 77 69 6c 6c 20  th no data will 
0280: 66 6f 72 63 65 20 61 20 66 6c 75 73 68 2e 0a 66  force a flush..f
0290: 75 6e 63 20 43 6f 6d 70 72 65 73 73 6f 72 28 77  unc Compressor(w
02a0: 72 69 74 65 72 20 69 6f 2e 57 72 69 74 65 72 29  riter io.Writer)
02b0: 20 69 6f 2e 57 72 69 74 65 72 20 7b 0a 09 76 61   io.Writer {..va
02c0: 72 20 63 74 78 20 63 6f 6e 74 65 78 74 0a 09 63  r ctx context..c
02d0: 74 78 2e 69 6e 70 75 74 20 3d 20 6d 61 6b 65 28  tx.input = make(
02e0: 5b 5d 62 79 74 65 2c 20 30 2c 20 38 29 0a 0a 09  []byte, 0, 8)...
02f0: 2f 2f 20 46 6f 72 77 61 72 64 20 64 65 63 6c 61  // Forward decla
0300: 72 61 74 69 6f 6e 20 61 73 20 69 74 20 69 73 20  ration as it is 
0310: 72 65 71 75 69 72 65 64 20 66 6f 72 20 72 65 63  required for rec
0320: 75 72 73 69 6f 6e 0a 09 76 61 72 20 77 72 69 74  ursion..var writ
0330: 65 20 63 6f 6d 70 72 65 73 73 6f 72 0a 0a 09 77  e compressor...w
0340: 72 69 74 65 20 3d 20 66 75 6e 63 28 64 61 74 61  rite = func(data
0350: 20 5b 5d 62 79 74 65 29 20 65 72 72 6f 72 20 7b   []byte) error {
0360: 0a 09 09 76 61 72 20 28 0a 09 09 09 62 6c 6f 63  ...var (....bloc
0370: 6b 53 69 7a 65 20 20 20 20 69 6e 74 20 3d 20 38  kSize    int = 8
0380: 0a 09 09 09 62 75 66 66 65 72 4c 65 6e 67 74 68  ....bufferLength
0390: 20 69 6e 74 20 3d 20 6c 65 6e 28 63 74 78 2e 69   int = len(ctx.i
03a0: 6e 70 75 74 29 0a 09 09 29 0a 0a 09 09 2f 2f 20  nput)...)....// 
03b0: 46 6f 72 63 65 20 61 20 66 6c 75 73 68 20 69 66  Force a flush if
03c0: 20 77 65 20 61 72 65 20 63 61 6c 6c 65 64 20 77   we are called w
03d0: 69 74 68 20 6e 6f 20 64 61 74 61 20 74 6f 20 77  ith no data to w
03e0: 72 69 74 65 0a 09 09 69 66 20 6c 65 6e 28 64 61  rite...if len(da
03f0: 74 61 29 20 3d 3d 20 30 20 7b 0a 09 09 09 2f 2f  ta) == 0 {....//
0400: 20 4e 6f 74 68 69 6e 67 20 74 6f 20 66 6c 75 73   Nothing to flus
0410: 68 20 69 66 20 74 68 65 20 62 75 66 66 65 72 20  h if the buffer 
0420: 69 73 20 65 6d 70 74 79 20 74 68 6f 75 67 68 0a  is empty though.
0430: 09 09 09 69 66 20 6c 65 6e 28 63 74 78 2e 69 6e  ...if len(ctx.in
0440: 70 75 74 29 20 3d 3d 20 30 20 7b 0a 09 09 09 09  put) == 0 {.....
0450: 72 65 74 75 72 6e 20 6e 69 6c 0a 09 09 09 7d 0a  return nil....}.
0460: 09 09 09 2f 2f 20 57 65 20 63 61 6e 27 74 20 68  ...// We can't h
0470: 61 76 65 20 6d 6f 72 65 20 74 68 61 6e 20 37 20  ave more than 7 
0480: 62 79 74 65 73 20 69 6e 20 74 68 65 20 62 75 66  bytes in the buf
0490: 66 65 72 20 73 6f 20 74 68 69 73 20 69 73 20 73  fer so this is s
04a0: 61 66 65 0a 09 09 09 64 61 74 61 2c 20 62 6c 6f  afe....data, blo
04b0: 63 6b 53 69 7a 65 2c 20 62 75 66 66 65 72 4c 65  ckSize, bufferLe
04c0: 6e 67 74 68 20 3d 20 63 74 78 2e 69 6e 70 75 74  ngth = ctx.input
04d0: 2c 20 6c 65 6e 28 63 74 78 2e 69 6e 70 75 74 29  , len(ctx.input)
04e0: 2c 20 30 0a 09 09 7d 0a 0a 09 09 2f 2f 20 43 68  , 0...}....// Ch
04f0: 65 63 6b 20 69 66 20 74 68 65 72 65 20 61 72 65  eck if there are
0500: 20 70 65 6e 64 69 6e 67 20 62 79 74 65 73 20 69   pending bytes i
0510: 6e 20 74 68 65 20 62 75 66 66 65 72 0a 09 09 69  n the buffer...i
0520: 66 20 6c 65 6e 28 64 61 74 61 29 20 3c 20 62 6c  f len(data) < bl
0530: 6f 63 6b 53 69 7a 65 20 7c 7c 20 62 75 66 66 65  ockSize || buffe
0540: 72 4c 65 6e 67 74 68 20 3e 20 30 20 7b 0a 0a 09  rLength > 0 {...
0550: 09 09 2f 2f 20 49 66 20 74 68 65 20 63 75 72 72  ..// If the curr
0560: 65 6e 74 20 62 75 66 66 65 72 20 2b 20 6e 65 77  ent buffer + new
0570: 20 64 61 74 61 20 63 61 6e 20 66 69 74 20 69 6e   data can fit in
0580: 74 6f 20 61 20 62 6c 6f 63 6b 0a 09 09 09 69 66  to a block....if
0590: 20 28 6c 65 6e 28 64 61 74 61 29 20 2b 20 62 75   (len(data) + bu
05a0: 66 66 65 72 4c 65 6e 67 74 68 29 20 3c 3d 20 62  fferLength) <= b
05b0: 6c 6f 63 6b 53 69 7a 65 20 7b 0a 09 09 09 09 63  lockSize {.....c
05c0: 74 78 2e 69 6e 70 75 74 20 3d 20 61 70 70 65 6e  tx.input = appen
05d0: 64 28 63 74 78 2e 69 6e 70 75 74 2c 20 64 61 74  d(ctx.input, dat
05e0: 61 2e 2e 2e 29 0a 0a 09 09 09 09 2f 2f 20 46 6c  a...)......// Fl
05f0: 75 73 68 20 74 68 65 20 62 6c 6f 63 6b 20 69 66  ush the block if
0600: 20 74 68 65 20 62 75 66 66 65 72 20 66 69 6c 6c   the buffer fill
0610: 73 20 69 74 0a 09 09 09 09 69 66 20 6c 65 6e 28  s it.....if len(
0620: 63 74 78 2e 69 6e 70 75 74 29 20 3d 3d 20 62 6c  ctx.input) == bl
0630: 6f 63 6b 53 69 7a 65 20 7b 0a 09 09 09 09 09 72  ockSize {......r
0640: 65 74 75 72 6e 20 77 72 69 74 65 28 6e 69 6c 29  eturn write(nil)
0650: 0a 09 09 09 09 7d 0a 09 09 09 09 2f 2f 20 2e 2e  .....}.....// ..
0660: 2e 20 6f 74 68 65 72 77 69 73 65 20 6a 75 73 74  . otherwise just
0670: 20 72 65 74 75 72 6e 0a 09 09 09 09 72 65 74 75   return.....retu
0680: 72 6e 20 6e 69 6c 0a 09 09 09 7d 0a 0a 09 09 09  rn nil....}.....
0690: 2f 2f 20 54 68 65 20 63 75 72 72 65 6e 74 20 62  // The current b
06a0: 75 66 66 65 72 20 2b 20 6e 65 77 20 64 61 74 61  uffer + new data
06b0: 20 6f 76 65 72 66 6c 6f 77 20 74 68 65 20 62 6c   overflow the bl
06c0: 6f 63 6b 20 73 69 7a 65 0a 09 09 09 2f 2f 20 43  ock size....// C
06d0: 6f 6d 70 6c 65 74 65 20 74 68 65 20 62 6c 6f 63  omplete the bloc
06e0: 6b 2c 20 66 6c 75 73 68 20 69 74 20 2e 2e 2e 0a  k, flush it ....
06f0: 09 09 09 63 74 78 2e 69 6e 70 75 74 20 3d 20 61  ...ctx.input = a
0700: 70 70 65 6e 64 28 63 74 78 2e 69 6e 70 75 74 2c  ppend(ctx.input,
0710: 20 64 61 74 61 5b 3a 62 6c 6f 63 6b 53 69 7a 65   data[:blockSize
0720: 2d 62 75 66 66 65 72 4c 65 6e 67 74 68 5d 2e 2e  -bufferLength]..
0730: 2e 29 0a 09 09 09 69 66 20 65 72 72 20 3a 3d 20  .)....if err := 
0740: 77 72 69 74 65 28 6e 69 6c 29 3b 20 65 72 72 20  write(nil); err 
0750: 21 3d 20 6e 69 6c 20 7b 0a 09 09 09 09 72 65 74  != nil {.....ret
0760: 75 72 6e 20 65 72 72 0a 09 09 09 7d 0a 09 09 09  urn err....}....
0770: 2f 2f 20 2e 2e 2e 20 61 6e 64 20 73 74 61 67 65  // ... and stage
0780: 20 74 68 65 20 72 65 73 74 20 6f 66 20 74 68 65   the rest of the
0790: 20 64 61 74 61 20 69 6e 20 74 68 65 20 62 75 66   data in the buf
07a0: 66 65 72 0a 09 09 09 63 74 78 2e 69 6e 70 75 74  fer....ctx.input
07b0: 20 3d 20 61 70 70 65 6e 64 28 63 74 78 2e 69 6e   = append(ctx.in
07c0: 70 75 74 2c 20 64 61 74 61 5b 62 6c 6f 63 6b 53  put, data[blockS
07d0: 69 7a 65 2d 62 75 66 66 65 72 4c 65 6e 67 74 68  ize-bufferLength
07e0: 3a 5d 2e 2e 2e 29 0a 09 09 09 72 65 74 75 72 6e  :]...)....return
07f0: 20 6e 69 6c 0a 09 09 7d 0a 0a 09 09 76 61 72 20   nil...}....var 
0800: 62 75 66 20 5b 5d 62 79 74 65 20 3d 20 6d 61 6b  buf []byte = mak
0810: 65 28 5b 5d 62 79 74 65 2c 20 31 2c 20 62 6c 6f  e([]byte, 1, blo
0820: 63 6b 53 69 7a 65 2b 31 29 0a 09 09 66 6f 72 20  ckSize+1)...for 
0830: 62 6c 6f 63 6b 20 3a 3d 20 30 3b 20 62 6c 6f 63  block := 0; bloc
0840: 6b 20 3c 20 6c 65 6e 28 64 61 74 61 29 2f 62 6c  k < len(data)/bl
0850: 6f 63 6b 53 69 7a 65 3b 20 62 6c 6f 63 6b 2b 2b  ockSize; block++
0860: 20 7b 0a 09 09 09 66 6f 72 20 69 20 3a 3d 20 30   {....for i := 0
0870: 3b 20 69 20 3c 20 62 6c 6f 63 6b 53 69 7a 65 3b  ; i < blockSize;
0880: 20 69 2b 2b 20 7b 0a 09 09 09 09 76 61 72 20 63   i++ {.....var c
0890: 75 72 72 65 6e 74 20 62 79 74 65 20 3d 20 64 61  urrent byte = da
08a0: 74 61 5b 28 62 6c 6f 63 6b 2a 62 6c 6f 63 6b 53  ta[(block*blockS
08b0: 69 7a 65 29 2b 69 5d 0a 09 09 09 09 69 66 20 63  ize)+i].....if c
08c0: 74 78 2e 74 61 62 6c 65 5b 63 74 78 2e 68 61 73  tx.table[ctx.has
08d0: 68 5d 20 3d 3d 20 63 75 72 72 65 6e 74 20 7b 0a  h] == current {.
08e0: 09 09 09 09 09 2f 2f 20 47 75 65 73 73 20 77 61  .....// Guess wa
08f0: 73 20 72 69 67 68 74 20 2d 20 64 6f 6e 27 74 20  s right - don't 
0900: 6f 75 74 70 75 74 0a 09 09 09 09 09 62 75 66 5b  output......buf[
0910: 30 5d 20 7c 3d 20 31 20 3c 3c 20 75 69 6e 74 28  0] |= 1 << uint(
0920: 69 29 0a 09 09 09 09 7d 20 65 6c 73 65 20 7b 0a  i).....} else {.
0930: 09 09 09 09 09 2f 2f 20 47 75 65 73 73 20 77 61  .....// Guess wa
0940: 73 20 77 72 6f 6e 67 2c 20 6f 75 74 70 75 74 20  s wrong, output 
0950: 63 68 61 72 0a 09 09 09 09 09 63 74 78 2e 74 61  char......ctx.ta
0960: 62 6c 65 5b 63 74 78 2e 68 61 73 68 5d 20 3d 20  ble[ctx.hash] = 
0970: 63 75 72 72 65 6e 74 0a 09 09 09 09 09 62 75 66  current......buf
0980: 20 3d 20 61 70 70 65 6e 64 28 62 75 66 2c 20 63   = append(buf, c
0990: 75 72 72 65 6e 74 29 0a 09 09 09 09 7d 0a 09 09  urrent).....}...
09a0: 09 09 63 74 78 2e 68 61 73 68 20 3d 20 28 63 74  ..ctx.hash = (ct
09b0: 78 2e 68 61 73 68 20 3c 3c 20 34 29 20 5e 20 75  x.hash << 4) ^ u
09c0: 69 6e 74 31 36 28 63 75 72 72 65 6e 74 29 0a 09  int16(current)..
09d0: 09 09 7d 0a 0a 09 09 09 69 66 20 5f 2c 20 65 72  ..}.....if _, er
09e0: 72 20 3a 3d 20 77 72 69 74 65 72 2e 57 72 69 74  r := writer.Writ
09f0: 65 28 62 75 66 29 3b 20 65 72 72 20 21 3d 20 6e  e(buf); err != n
0a00: 69 6c 20 7b 0a 09 09 09 09 72 65 74 75 72 6e 20  il {.....return 
0a10: 65 72 72 0a 09 09 09 7d 0a 0a 09 09 09 2f 2f 20  err....}.....// 
0a20: 52 65 73 65 74 20 74 68 65 20 66 6c 61 67 73 20  Reset the flags 
0a30: 61 6e 64 20 62 75 66 66 65 72 20 66 6f 72 20 74  and buffer for t
0a40: 68 65 20 6e 65 78 74 20 69 74 65 72 61 74 69 6f  he next iteratio
0a50: 6e 0a 09 09 09 62 75 66 2c 20 62 75 66 5b 30 5d  n....buf, buf[0]
0a60: 20 3d 20 62 75 66 5b 3a 31 5d 2c 20 30 0a 09 09   = buf[:1], 0...
0a70: 7d 0a 0a 09 09 69 66 20 72 65 6d 61 69 6e 69 6e  }....if remainin
0a80: 67 20 3a 3d 20 6c 65 6e 28 64 61 74 61 29 20 25  g := len(data) %
0a90: 20 62 6c 6f 63 6b 53 69 7a 65 3b 20 72 65 6d 61   blockSize; rema
0aa0: 69 6e 69 6e 67 20 3e 20 30 20 7b 0a 09 09 09 63  ining > 0 {....c
0ab0: 74 78 2e 69 6e 70 75 74 20 3d 20 63 74 78 2e 69  tx.input = ctx.i
0ac0: 6e 70 75 74 5b 3a 72 65 6d 61 69 6e 69 6e 67 5d  nput[:remaining]
0ad0: 0a 09 09 09 63 6f 70 79 28 63 74 78 2e 69 6e 70  ....copy(ctx.inp
0ae0: 75 74 2c 20 64 61 74 61 5b 6c 65 6e 28 64 61 74  ut, data[len(dat
0af0: 61 29 2d 72 65 6d 61 69 6e 69 6e 67 3a 5d 29 0a  a)-remaining:]).
0b00: 09 09 7d 20 65 6c 73 65 20 7b 0a 09 09 09 63 74  ..} else {....ct
0b10: 78 2e 69 6e 70 75 74 20 3d 20 63 74 78 2e 69 6e  x.input = ctx.in
0b20: 70 75 74 5b 3a 30 5d 0a 09 09 7d 0a 0a 09 09 72  put[:0]...}....r
0b30: 65 74 75 72 6e 20 6e 69 6c 0a 09 7d 0a 0a 09 72  eturn nil..}...r
0b40: 65 74 75 72 6e 20 77 72 69 74 65 0a 7d 0a 0a 2f  eturn write.}../
0b50: 2f 20 41 20 66 75 6e 63 74 69 6f 6e 20 74 79 70  / A function typ
0b60: 65 20 61 6c 69 61 73 20 73 6f 20 74 68 61 74 20  e alias so that 
0b70: 69 74 20 63 61 6e 20 68 61 76 65 20 6d 65 74 68  it can have meth
0b80: 6f 64 73 20 61 74 74 61 63 68 65 64 20 74 6f 20  ods attached to 
0b90: 69 74 0a 74 79 70 65 20 64 65 63 6f 6d 70 72 65  it.type decompre
0ba0: 73 73 6f 72 20 66 75 6e 63 28 5b 5d 62 79 74 65  ssor func([]byte
0bb0: 29 20 28 69 6e 74 2c 20 65 72 72 6f 72 29 0a 0a  ) (int, error)..
0bc0: 2f 2f 20 52 65 71 75 69 72 65 64 20 74 6f 20 69  // Required to i
0bd0: 6d 70 6c 65 6d 65 6e 74 20 69 6f 2e 52 65 61 64  mplement io.Read
0be0: 65 72 0a 66 75 6e 63 20 28 72 20 64 65 63 6f 6d  er.func (r decom
0bf0: 70 72 65 73 73 6f 72 29 20 52 65 61 64 28 6f 75  pressor) Read(ou
0c00: 74 70 75 74 20 5b 5d 62 79 74 65 29 20 28 69 6e  tput []byte) (in
0c10: 74 2c 20 65 72 72 6f 72 29 20 7b 0a 09 72 65 74  t, error) {..ret
0c20: 75 72 6e 20 72 28 6f 75 74 70 75 74 29 0a 7d 0a  urn r(output).}.
0c30: 0a 2f 2f 20 52 65 74 75 72 6e 73 20 61 6e 20 69  .// Returns an i
0c40: 6f 2e 52 65 61 64 65 72 20 69 6d 70 6c 65 6d 65  o.Reader impleme
0c50: 6e 74 61 74 69 6f 6e 20 74 68 61 74 20 77 72 61  ntation that wra
0c60: 70 73 20 74 68 65 20 70 72 6f 76 69 64 65 64 20  ps the provided 
0c70: 69 6f 2e 52 65 61 64 65 72 0a 2f 2f 20 61 6e 64  io.Reader.// and
0c80: 20 64 65 63 6f 6d 70 72 65 73 73 65 73 20 64 61   decompresses da
0c90: 74 61 20 61 63 63 6f 72 64 69 6e 67 20 74 6f 20  ta according to 
0ca0: 74 68 65 20 70 72 65 64 69 63 74 6f 72 20 61 6c  the predictor al
0cb0: 67 6f 72 69 74 68 6d 0a 66 75 6e 63 20 44 65 63  gorithm.func Dec
0cc0: 6f 6d 70 72 65 73 73 6f 72 28 72 65 61 64 65 72  ompressor(reader
0cd0: 20 69 6f 2e 52 65 61 64 65 72 29 20 69 6f 2e 52   io.Reader) io.R
0ce0: 65 61 64 65 72 20 7b 0a 09 76 61 72 20 63 74 78  eader {..var ctx
0cf0: 20 63 6f 6e 74 65 78 74 0a 09 63 74 78 2e 69 6e   context..ctx.in
0d00: 70 75 74 20 3d 20 6d 61 6b 65 28 5b 5d 62 79 74  put = make([]byt
0d10: 65 2c 20 30 2c 20 38 29 0a 0a 09 72 65 74 75 72  e, 0, 8)...retur
0d20: 6e 20 64 65 63 6f 6d 70 72 65 73 73 6f 72 28 66  n decompressor(f
0d30: 75 6e 63 28 6f 75 74 70 75 74 20 5b 5d 62 79 74  unc(output []byt
0d40: 65 29 20 28 69 6e 74 2c 20 65 72 72 6f 72 29 20  e) (int, error) 
0d50: 7b 0a 09 09 76 61 72 20 28 0a 09 09 09 65 72 72  {...var (....err
0d60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0d70: 20 20 20 20 20 20 65 72 72 6f 72 0a 09 09 09 66        error....f
0d80: 6c 61 67 73 20 20 20 20 20 20 20 20 20 20 20 20  lags            
0d90: 20 20 20 20 20 20 20 20 62 79 74 65 0a 09 09 09          byte....
0da0: 72 63 2c 20 61 76 61 69 6c 61 62 6c 65 2c 20 70  rc, available, p
0db0: 72 65 64 69 63 74 65 64 20 69 6e 74 0a 09 09 29  redicted int...)
0dc0: 0a 0a 09 09 2f 2f 20 53 61 6e 69 74 79 20 63 68  ....// Sanity ch
0dd0: 65 63 6b 20 66 6f 72 20 73 70 61 63 65 20 74 6f  eck for space to
0de0: 20 72 65 61 64 20 69 6e 74 6f 0a 09 09 69 66 20   read into...if 
0df0: 6c 65 6e 28 6f 75 74 70 75 74 29 20 3d 3d 20 30  len(output) == 0
0e00: 20 7b 0a 09 09 09 72 65 74 75 72 6e 20 30 2c 20   {....return 0, 
0e10: 6e 69 6c 0a 09 09 7d 0a 0a 09 09 2f 2f 20 43 68  nil...}....// Ch
0e20: 65 63 6b 20 77 68 65 74 68 65 72 20 77 65 20 68  eck whether we h
0e30: 61 76 65 20 6c 65 66 74 6f 76 65 72 20 64 61 74  ave leftover dat
0e40: 61 20 69 6e 20 74 68 65 20 62 75 66 66 65 72 0a  a in the buffer.
0e50: 09 09 69 66 20 6c 65 6e 28 63 74 78 2e 69 6e 70  ..if len(ctx.inp
0e60: 75 74 29 20 3e 20 30 20 7b 0a 09 09 09 72 63 20  ut) > 0 {....rc 
0e70: 3d 20 63 6f 70 79 28 6f 75 74 70 75 74 2c 20 63  = copy(output, c
0e80: 74 78 2e 69 6e 70 75 74 29 0a 0a 09 09 09 2f 2f  tx.input).....//
0e90: 20 43 68 65 63 6b 20 77 68 65 74 68 65 72 20 77   Check whether w
0ea0: 65 20 73 74 69 6c 6c 20 68 61 76 65 20 6c 65 66  e still have lef
0eb0: 74 6f 76 65 72 20 64 61 74 61 20 69 6e 20 74 68  tover data in th
0ec0: 65 20 62 75 66 66 65 72 20 3a 29 0a 09 09 09 69  e buffer :)....i
0ed0: 66 20 72 63 20 3c 20 6c 65 6e 28 63 74 78 2e 69  f rc < len(ctx.i
0ee0: 6e 70 75 74 29 20 7b 0a 09 09 09 09 63 74 78 2e  nput) {.....ctx.
0ef0: 69 6e 70 75 74 20 3d 20 63 74 78 2e 69 6e 70 75  input = ctx.inpu
0f00: 74 5b 3a 63 6f 70 79 28 63 74 78 2e 69 6e 70 75  t[:copy(ctx.inpu
0f10: 74 2c 20 63 74 78 2e 69 6e 70 75 74 5b 72 63 3a  t, ctx.input[rc:
0f20: 5d 29 5d 0a 09 09 09 7d 0a 09 09 09 72 65 74 75  ])]....}....retu
0f30: 72 6e 20 72 63 2c 20 6e 69 6c 0a 09 09 7d 0a 0a  rn rc, nil...}..
0f40: 09 09 2f 2f 20 52 65 61 64 20 74 68 65 20 6e 65  ..// Read the ne
0f50: 78 74 20 70 72 65 64 69 63 74 69 6f 6e 20 68 65  xt prediction he
0f60: 61 64 65 72 0a 09 09 72 63 2c 20 65 72 72 20 3d  ader...rc, err =
0f70: 20 72 65 61 64 65 72 2e 52 65 61 64 28 63 74 78   reader.Read(ctx
0f80: 2e 69 6e 70 75 74 5b 3a 31 5d 29 0a 09 09 2f 2f  .input[:1])...//
0f90: 20 46 61 69 6c 20 6f 6e 20 65 72 72 6f 72 20 75   Fail on error u
0fa0: 6e 6c 65 73 73 20 69 74 20 69 73 20 45 4f 46 0a  nless it is EOF.
0fb0: 09 09 69 66 20 65 72 72 20 21 3d 20 6e 69 6c 20  ..if err != nil 
0fc0: 26 26 20 65 72 72 20 21 3d 20 69 6f 2e 45 4f 46  && err != io.EOF
0fd0: 20 7b 0a 09 09 09 72 65 74 75 72 6e 20 30 2c 20   {....return 0, 
0fe0: 65 72 72 0a 09 09 7d 20 65 6c 73 65 20 69 66 20  err...} else if 
0ff0: 72 63 20 3d 3d 20 30 20 7b 0a 09 09 09 72 65 74  rc == 0 {....ret
1000: 75 72 6e 20 30 2c 20 65 72 72 0a 09 09 7d 0a 0a  urn 0, err...}..
1010: 09 09 2f 2f 20 45 78 74 65 6e 64 20 74 68 65 20  ..// Extend the 
1020: 62 75 66 66 65 72 2c 20 63 6f 70 79 20 74 68 65  buffer, copy the
1030: 20 70 72 65 64 69 63 74 69 6f 6e 20 68 65 61 64   prediction head
1040: 65 72 0a 09 09 2f 2f 20 20 61 6e 64 20 63 61 6c  er...//  and cal
1050: 63 75 6c 61 74 65 20 74 68 65 20 6e 75 6d 62 65  culate the numbe
1060: 72 20 6f 66 20 73 75 62 73 65 71 75 65 6e 74 20  r of subsequent 
1070: 62 79 74 65 73 20 74 6f 20 72 65 61 64 0a 09 09  bytes to read...
1080: 63 74 78 2e 69 6e 70 75 74 20 3d 20 63 74 78 2e  ctx.input = ctx.
1090: 69 6e 70 75 74 5b 3a 38 5d 0a 09 09 66 6c 61 67  input[:8]...flag
10a0: 73 20 3d 20 63 74 78 2e 69 6e 70 75 74 5b 30 5d  s = ctx.input[0]
10b0: 0a 09 09 70 72 65 64 69 63 74 65 64 20 3d 20 69  ...predicted = i
10c0: 6e 74 28 62 69 74 73 2e 48 61 6d 6d 69 6e 67 28  nt(bits.Hamming(
10d0: 66 6c 61 67 73 29 29 0a 09 09 61 76 61 69 6c 61  flags))...availa
10e0: 62 6c 65 20 3d 20 38 20 2d 20 70 72 65 64 69 63  ble = 8 - predic
10f0: 74 65 64 0a 0a 09 09 2f 2f 20 52 65 61 64 20 74  ted....// Read t
1100: 68 65 20 6e 6f 6e 2d 70 72 65 64 69 63 74 65 64  he non-predicted
1110: 20 62 79 74 65 73 20 61 6e 64 20 70 6c 61 63 65   bytes and place
1120: 20 74 68 65 6d 20 69 6e 20 74 68 65 20 65 6e 64   them in the end
1130: 20 6f 66 20 74 68 65 20 62 75 66 66 65 72 0a 09   of the buffer..
1140: 09 72 63 2c 20 65 72 72 20 3d 20 72 65 61 64 65  .rc, err = reade
1150: 72 2e 52 65 61 64 28 63 74 78 2e 69 6e 70 75 74  r.Read(ctx.input
1160: 5b 70 72 65 64 69 63 74 65 64 3a 5d 29 0a 09 72  [predicted:])..r
1170: 65 74 72 79 44 61 74 61 3a 0a 09 09 69 66 20 72  etryData:...if r
1180: 63 20 3c 20 69 6e 74 28 61 76 61 69 6c 61 62 6c  c < int(availabl
1190: 65 29 20 26 26 20 65 72 72 20 3d 3d 20 6e 69 6c  e) && err == nil
11a0: 20 7b 0a 09 09 09 2f 2f 20 52 65 74 72 79 20 74   {....// Retry t
11b0: 68 65 20 72 65 61 64 20 69 66 20 77 65 20 68 61  he read if we ha
11c0: 76 65 20 66 65 77 65 72 20 62 79 74 65 73 20 74  ve fewer bytes t
11d0: 68 61 6e 20 77 68 61 74 20 74 68 65 20 70 72 65  han what the pre
11e0: 64 69 63 74 69 6f 6e 20 68 65 61 64 65 72 20 69  diction header i
11f0: 6e 64 69 63 61 74 65 73 0a 09 09 09 76 61 72 20  ndicates....var 
1200: 72 63 20 69 6e 74 0a 09 09 09 72 63 2c 20 65 72  rc int....rc, er
1210: 72 20 3d 20 72 65 61 64 65 72 2e 52 65 61 64 28  r = reader.Read(
1220: 63 74 78 2e 69 6e 70 75 74 5b 70 72 65 64 69 63  ctx.input[predic
1230: 74 65 64 2b 72 63 3a 5d 29 0a 09 09 09 72 63 20  ted+rc:])....rc 
1240: 2b 3d 20 72 63 0a 09 09 09 67 6f 74 6f 20 72 65  += rc....goto re
1250: 74 72 79 44 61 74 61 0a 09 09 7d 20 2f 2f 20 43  tryData...} // C
1260: 6f 6e 74 69 6e 75 65 20 6f 6e 20 61 6e 79 20 65  ontinue on any e
1270: 72 72 6f 72 2c 20 74 72 79 20 74 6f 20 64 65 63  rror, try to dec
1280: 6f 6d 70 72 65 73 73 20 61 6e 64 20 72 65 74 75  ompress and retu
1290: 72 6e 20 69 74 20 61 6c 6f 6e 67 20 74 68 65 20  rn it along the 
12a0: 72 65 73 75 6c 74 0a 0a 09 09 2f 2f 20 57 61 6c  result....// Wal
12b0: 6b 20 74 68 65 20 62 75 66 66 65 72 2c 20 66 69  k the buffer, fi
12c0: 6c 6c 69 6e 67 20 69 6e 20 74 68 65 20 70 72 65  lling in the pre
12d0: 64 69 63 74 65 64 20 62 6c 61 6e 6b 73 2c 0a 09  dicted blanks,..
12e0: 09 2f 2f 20 72 65 6c 6f 63 61 74 69 6e 67 20 72  .// relocating r
12f0: 65 61 64 20 62 79 74 65 73 20 61 6e 64 20 61 6e  ead bytes and an
1300: 64 20 75 70 64 61 74 69 6e 67 20 74 68 65 20 67  d updating the g
1310: 75 65 73 73 20 74 61 62 6c 65 0a 09 09 66 6f 72  uess table...for
1320: 20 69 2c 20 61 20 3a 3d 20 75 69 6e 74 28 30 29   i, a := uint(0)
1330: 2c 20 70 72 65 64 69 63 74 65 64 3b 20 69 20 3c  , predicted; i <
1340: 20 38 3b 20 69 2b 2b 20 7b 0a 09 09 09 69 66 20   8; i++ {....if 
1350: 28 66 6c 61 67 73 20 26 20 28 31 20 3c 3c 20 69  (flags & (1 << i
1360: 29 29 20 3e 20 30 20 7b 0a 09 09 09 09 2f 2f 20  )) > 0 {.....// 
1370: 47 75 65 73 73 20 73 75 63 63 65 65 64 65 64 2c  Guess succeeded,
1380: 20 66 69 6c 6c 20 69 6e 20 66 72 6f 6d 20 74 68   fill in from th
1390: 65 20 74 61 62 6c 65 0a 09 09 09 09 63 74 78 2e  e table.....ctx.
13a0: 69 6e 70 75 74 5b 69 5d 20 3d 20 63 74 78 2e 74  input[i] = ctx.t
13b0: 61 62 6c 65 5b 63 74 78 2e 68 61 73 68 5d 0a 09  able[ctx.hash]..
13c0: 09 09 09 72 63 2b 2b 0a 09 09 09 7d 20 65 6c 73  ...rc++....} els
13d0: 65 20 7b 0a 09 09 09 09 2f 2f 20 52 65 6c 6f 63  e {.....// Reloc
13e0: 61 74 65 20 61 20 72 65 61 64 20 62 79 74 65 0a  ate a read byte.
13f0: 09 09 09 09 63 74 78 2e 69 6e 70 75 74 5b 69 5d  ....ctx.input[i]
1400: 2c 20 61 20 3d 20 63 74 78 2e 69 6e 70 75 74 5b  , a = ctx.input[
1410: 61 5d 2c 20 61 2b 31 0a 09 09 09 09 2f 2f 20 47  a], a+1.....// G
1420: 75 65 73 73 20 66 61 69 6c 65 64 2c 20 75 70 64  uess failed, upd
1430: 61 74 65 20 74 68 65 20 74 61 62 6c 65 0a 09 09  ate the table...
1440: 09 09 63 74 78 2e 74 61 62 6c 65 5b 63 74 78 2e  ..ctx.table[ctx.
1450: 68 61 73 68 5d 20 3d 20 63 74 78 2e 69 6e 70 75  hash] = ctx.inpu
1460: 74 5b 69 5d 0a 09 09 09 7d 0a 09 09 09 2f 2f 20  t[i]....}....// 
1470: 55 70 64 61 74 65 20 74 68 65 20 68 61 73 68 0a  Update the hash.
1480: 09 09 09 63 74 78 2e 68 61 73 68 20 3d 20 28 63  ...ctx.hash = (c
1490: 74 78 2e 68 61 73 68 20 3c 3c 20 34 29 20 5e 20  tx.hash << 4) ^ 
14a0: 75 69 6e 74 31 36 28 63 74 78 2e 69 6e 70 75 74  uint16(ctx.input
14b0: 5b 69 5d 29 0a 09 09 7d 0a 0a 09 09 2f 2f 20 72  [i])...}....// r
14c0: 63 20 6e 6f 77 20 63 6f 6e 74 61 69 6e 73 20 74  c now contains t
14d0: 68 65 20 70 72 65 63 69 73 65 20 61 6d 6f 75 6e  he precise amoun
14e0: 74 20 6f 66 20 70 6f 70 75 6c 61 74 65 64 20 64  t of populated d
14f0: 61 74 61 0a 09 09 63 74 78 2e 69 6e 70 75 74 20  ata...ctx.input 
1500: 3d 20 63 74 78 2e 69 6e 70 75 74 5b 3a 72 63 5d  = ctx.input[:rc]
1510: 0a 09 09 61 76 61 69 6c 61 62 6c 65 20 3d 20 63  ...available = c
1520: 6f 70 79 28 6f 75 74 70 75 74 2c 20 63 74 78 2e  opy(output, ctx.
1530: 69 6e 70 75 74 29 0a 0a 09 09 2f 2f 20 43 68 65  input)....// Che
1540: 63 6b 20 66 6f 72 20 72 65 6d 61 69 6e 69 6e 67  ck for remaining
1550: 20 62 79 74 65 73 20 74 68 61 74 20 64 6f 6e 74   bytes that dont
1560: 20 66 69 74 20 69 6e 20 74 68 65 20 6f 75 74 70   fit in the outp
1570: 75 74 20 62 75 66 66 65 72 0a 09 09 69 66 20 61  ut buffer...if a
1580: 76 61 69 6c 61 62 6c 65 20 3c 20 72 63 20 7b 0a  vailable < rc {.
1590: 09 09 09 63 74 78 2e 69 6e 70 75 74 20 3d 20 63  ...ctx.input = c
15a0: 74 78 2e 69 6e 70 75 74 5b 3a 63 6f 70 79 28 63  tx.input[:copy(c
15b0: 74 78 2e 69 6e 70 75 74 2c 20 63 74 78 2e 69 6e  tx.input, ctx.in
15c0: 70 75 74 5b 61 76 61 69 6c 61 62 6c 65 3a 5d 29  put[available:])
15d0: 5d 0a 09 09 7d 20 65 6c 73 65 20 7b 0a 09 09 09  ]...} else {....
15e0: 2f 2f 20 43 6c 65 61 72 20 74 68 65 20 62 75 66  // Clear the buf
15f0: 66 65 72 0a 09 09 09 63 74 78 2e 69 6e 70 75 74  fer....ctx.input
1600: 20 3d 20 63 74 78 2e 69 6e 70 75 74 5b 3a 30 5d   = ctx.input[:0]
1610: 0a 09 09 7d 0a 0a 09 09 72 65 74 75 72 6e 20 61  ...}....return a
1620: 76 61 69 6c 61 62 6c 65 2c 20 65 72 72 0a 09 7d  vailable, err..}
1630: 29 0a 7d 0a                                      ).}.