encapsulation/encapsulation.go

   1 // Package encapsulation implements a way of encoding variable-size chunks of
   2 // data and padding into a byte stream.
   3 //
   4 // Each chunk of data or padding starts with a variable-size length prefix. One
   5 // bit ("d") in the first byte of the prefix indicates whether the chunk
   6 // represents data or padding (1=data, 0=padding). Another bit ("c" for
   7 // "continuation") is the indicates whether there are more bytes in the length
   8 // prefix. The remaining 6 bits ("x") encode part of the length value.
   9 //      dcxxxxxx
  10 // If the continuation bit is set, then the next byte is also part of the length
  11 // prefix. It lacks the "d" bit, has its own "c" bit, and 7 value-carrying bits
  12 // ("y").
  13 //      cyyyyyyy
  14 // The length is decoded by concatenating value-carrying bits, from left to
  15 // right, of all value-carrying bits, up to and including the first byte whose
  16 // "c" bit is 0. Although in principle this encoding would allow for length
  17 // prefixes of any size, length prefixes are arbitrarily limited to 3 bytes and
  18 // any attempt to read or write a longer one is an error. These are therefore
  19 // the only valid formats:
  20 //      00xxxxxx                        xxxxxx₂ bytes of padding
  21 //      10xxxxxx                        xxxxxx₂ bytes of data
  22 //      01xxxxxx 0yyyyyyy               xxxxxxyyyyyyy₂ bytes of padding
  23 //      11xxxxxx 0yyyyyyy               xxxxxxyyyyyyy₂ bytes of data
  24 //      01xxxxxx 1yyyyyyy 0zzzzzzz      xxxxxxyyyyyyyzzzzzzz₂ bytes of padding
  25 //      11xxxxxx 1yyyyyyy 0zzzzzzz      xxxxxxyyyyyyyzzzzzzz₂ bytes of data
  26 // The maximum encodable length is 11111111111111111111₂ = 0xfffff = 1048575.
  27 // There is no requirement to use a length prefix of minimum size; i.e. 00000100
  28 // and 01000000 00000100 are both valid encodings of the value 4.
  29 //
  30 // After the length prefix follow that many bytes of padding or data. There are
  31 // no restrictions on the value of bytes comprising padding.
  32 //
  33 // The idea for this encapsulation is sketched here:
  34 // https://github.com/net4people/bbs/issues/9#issuecomment-524095186
  35 package encapsulation
  36
  37 import (
  38         "errors"
  39         "io"
  40         "io/ioutil"
  41 )
  42
  43 // ErrTooLong is the error returned when an encoded length prefix is longer than
  44 // 3 bytes, or when ReadData receives an input whose length is too large to
  45 // encode in a 3-byte length prefix.
  46 var ErrTooLong = errors.New("length prefix is too long")
  47
  48 // ReadData returns a new slice with the contents of the next available data
  49 // chunk, skipping over any padding chunks that may come first. The returned
  50 // error value is nil if and only if a data chunk was present and was read in
  51 // its entirety. The returned error is io.EOF only if r ended before the first
  52 // byte of a length prefix. If r ended in the middle of a length prefix or
  53 // data/padding, the returned error is io.ErrUnexpectedEOF.
  54 func ReadData(r io.Reader) ([]byte, error) {
  55         for {
  56                 var b [1]byte
  57                 _, err := r.Read(b[:])
  58                 if err != nil {
  59                         // This is the only place we may return a real io.EOF.
  60                         return nil, err
  61                 }
  62                 isData := (b[0] & 0x80) != 0
  63                 moreLength := (b[0] & 0x40) != 0
  64                 n := int(b[0] & 0x3f)
  65                 for i := 0; moreLength; i++ {
  66                         if i >= 2 {
  67                                 return nil, ErrTooLong
  68                         }
  69                         _, err := r.Read(b[:])
  70                         if err == io.EOF {
  71                                 err = io.ErrUnexpectedEOF
  72                         }
  73                         if err != nil {
  74                                 return nil, err
  75                         }
  76                         moreLength = (b[0] & 0x80) != 0
  77                         n = (n << 7) | int(b[0]&0x7f)
  78                 }
  79                 if isData {
  80                         p := make([]byte, n)
  81                         _, err := io.ReadFull(r, p)
  82                         if err == io.EOF {
  83                                 err = io.ErrUnexpectedEOF
  84                         }
  85                         if err != nil {
  86                                 return nil, err
  87                         }
  88                         return p, err
  89                 } else {
  90                         _, err := io.CopyN(ioutil.Discard, r, int64(n))
  91                         if err == io.EOF {
  92                                 err = io.ErrUnexpectedEOF
  93                         }
  94                         if err != nil {
  95                                 return nil, err
  96                         }
  97                 }
  98         }
  99 }
 100
 101 // dataPrefixForLength returns a length prefix for the given length, with the
 102 // "d" bit set to 1.
 103 func dataPrefixForLength(n int) ([]byte, error) {
 104         switch {
 105         case (n>>0)&0x3f == (n >> 0):
 106                 return []byte{0x80 | byte((n>>0)&0x3f)}, nil
 107         case (n>>7)&0x3f == (n >> 7):
 108                 return []byte{0xc0 | byte((n>>7)&0x3f), byte((n >> 0) & 0x7f)}, nil
 109         case (n>>14)&0x3f == (n >> 14):
 110                 return []byte{0xc0 | byte((n>>14)&0x3f), 0x80 | byte((n>>7)&0x7f), byte((n >> 0) & 0x7f)}, nil
 111         default:
 112                 return nil, ErrTooLong
 113         }
 114 }
 115
 116 // WriteData encodes a data chunk into w. It returns the total number of bytes
 117 // written; i.e., including the length prefix. The error is ErrTooLong if the
 118 // length of data cannot fit into a length prefix.
 119 func WriteData(w io.Writer, data []byte) (int, error) {
 120         prefix, err := dataPrefixForLength(len(data))
 121         if err != nil {
 122                 return 0, err
 123         }
 124         total := 0
 125         n, err := w.Write(prefix)
 126         total += n
 127         if err != nil {
 128                 return total, err
 129         }
 130         n, err = w.Write(data)
 131         total += n
 132         return total, err
 133 }
 134
 135 var paddingBuffer = make([]byte, 1024)
 136
 137 // WritePadding encodes padding chunks, whose total size (including their own
 138 // length prefixes) is n. Returns the total number of bytes written to w, which
 139 // will be exactly n unless there was an error. The error cannot be ErrTooLong
 140 // because this function will write multiple padding chunks if necessary to
 141 // reach the requested size. Panics if n is negative.
 142 func WritePadding(w io.Writer, n int) (int, error) {
 143         if n < 0 {
 144                 panic("negative length")
 145         }
 146         total := 0
 147         for n > 0 {
 148                 p := len(paddingBuffer)
 149                 if p > n {
 150                         p = n
 151                 }
 152                 n -= p
 153                 var prefix []byte
 154                 switch {
 155                 case ((p-1)>>0)&0x3f == ((p - 1) >> 0):
 156                         p = p - 1
 157                         prefix = []byte{byte((p >> 0) & 0x3f)}
 158                 case ((p-2)>>7)&0x3f == ((p - 2) >> 7):
 159                         p = p - 2
 160                         prefix = []byte{0x40 | byte((p>>7)&0x3f), byte((p >> 0) & 0x7f)}
 161                 case ((p-3)>>14)&0x3f == ((p - 3) >> 14):
 162                         p = p - 3
 163                         prefix = []byte{0x40 | byte((p>>14)&0x3f), 0x80 | byte((p>>7)&0x3f), byte((p >> 0) & 0x7f)}
 164                 }
 165                 nn, err := w.Write(prefix)
 166                 total += nn
 167                 if err != nil {
 168                         return total, err
 169                 }
 170                 nn, err = w.Write(paddingBuffer[:p])
 171                 total += nn
 172                 if err != nil {
 173                         return total, err
 174                 }
 175         }
 176         return total, nil
 177 }
 178
 179 // MaxDataForSize returns the length of the longest slice that can be passed to
 180 // WriteData, whose total encoded size (including length prefix) is no larger
 181 // than n. Call this to find out if a chunk of data will fit into a length
 182 // budget. Panics if n == 0.
 183 func MaxDataForSize(n int) int {
 184         if n == 0 {
 185                 panic("zero length")
 186         }
 187         prefix, err := dataPrefixForLength(n)
 188         if err == ErrTooLong {
 189                 return (1 << (6 + 7 + 7)) - 1 - 3
 190         } else if err != nil {
 191                 panic(err)
 192         }
 193         return n - len(prefix)
 194 }