1// Copyright (c) 2017 Couchbase, Inc. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package vellum 16 17import ( 18 "encoding/binary" 19 "fmt" 20 "io" 21) 22 23const versionV1 = 1 24const oneTransition = 1 << 7 25const transitionNext = 1 << 6 26const stateFinal = 1 << 6 27const footerSizeV1 = 16 28 29func init() { 30 registerEncoder(versionV1, func(w io.Writer) encoder { 31 return newEncoderV1(w) 32 }) 33} 34 35type encoderV1 struct { 36 bw *writer 37} 38 39func newEncoderV1(w io.Writer) *encoderV1 { 40 return &encoderV1{ 41 bw: newWriter(w), 42 } 43} 44 45func (e *encoderV1) reset(w io.Writer) { 46 e.bw.Reset(w) 47} 48 49func (e *encoderV1) start() error { 50 header := make([]byte, headerSize) 51 binary.LittleEndian.PutUint64(header, versionV1) 52 binary.LittleEndian.PutUint64(header[8:], uint64(0)) // type 53 n, err := e.bw.Write(header) 54 if err != nil { 55 return err 56 } 57 if n != headerSize { 58 return fmt.Errorf("short write of header %d/%d", n, headerSize) 59 } 60 return nil 61} 62 63func (e *encoderV1) encodeState(s *builderNode, lastAddr int) (int, error) { 64 if len(s.trans) == 0 && s.final && s.finalOutput == 0 { 65 return 0, nil 66 } else if len(s.trans) != 1 || s.final { 67 return e.encodeStateMany(s) 68 } else if !s.final && s.trans[0].out == 0 && s.trans[0].addr == lastAddr { 69 return e.encodeStateOneFinish(s, transitionNext) 70 } 71 return e.encodeStateOne(s) 72} 73 74func (e *encoderV1) encodeStateOne(s *builderNode) (int, error) { 75 start := uint64(e.bw.counter) 76 outPackSize := 0 77 if s.trans[0].out != 0 { 78 outPackSize = packedSize(s.trans[0].out) 79 err := e.bw.WritePackedUintIn(s.trans[0].out, outPackSize) 80 if err != nil { 81 return 0, err 82 } 83 } 84 delta := deltaAddr(start, uint64(s.trans[0].addr)) 85 transPackSize := packedSize(delta) 86 err := e.bw.WritePackedUintIn(delta, transPackSize) 87 if err != nil { 88 return 0, err 89 } 90 91 packSize := encodePackSize(transPackSize, outPackSize) 92 err = e.bw.WriteByte(packSize) 93 if err != nil { 94 return 0, err 95 } 96 97 return e.encodeStateOneFinish(s, 0) 98} 99 100func (e *encoderV1) encodeStateOneFinish(s *builderNode, next byte) (int, error) { 101 enc := encodeCommon(s.trans[0].in) 102 103 // not a common input 104 if enc == 0 { 105 err := e.bw.WriteByte(s.trans[0].in) 106 if err != nil { 107 return 0, err 108 } 109 } 110 err := e.bw.WriteByte(oneTransition | next | enc) 111 if err != nil { 112 return 0, err 113 } 114 115 return e.bw.counter - 1, nil 116} 117 118func (e *encoderV1) encodeStateMany(s *builderNode) (int, error) { 119 start := uint64(e.bw.counter) 120 transPackSize := 0 121 outPackSize := packedSize(s.finalOutput) 122 anyOutputs := s.finalOutput != 0 123 for i := range s.trans { 124 delta := deltaAddr(start, uint64(s.trans[i].addr)) 125 tsize := packedSize(delta) 126 if tsize > transPackSize { 127 transPackSize = tsize 128 } 129 osize := packedSize(s.trans[i].out) 130 if osize > outPackSize { 131 outPackSize = osize 132 } 133 anyOutputs = anyOutputs || s.trans[i].out != 0 134 } 135 if !anyOutputs { 136 outPackSize = 0 137 } 138 139 if anyOutputs { 140 // output final value 141 if s.final { 142 err := e.bw.WritePackedUintIn(s.finalOutput, outPackSize) 143 if err != nil { 144 return 0, err 145 } 146 } 147 // output transition values (in reverse) 148 for j := len(s.trans) - 1; j >= 0; j-- { 149 err := e.bw.WritePackedUintIn(s.trans[j].out, outPackSize) 150 if err != nil { 151 return 0, err 152 } 153 } 154 } 155 156 // output transition dests (in reverse) 157 for j := len(s.trans) - 1; j >= 0; j-- { 158 delta := deltaAddr(start, uint64(s.trans[j].addr)) 159 err := e.bw.WritePackedUintIn(delta, transPackSize) 160 if err != nil { 161 return 0, err 162 } 163 } 164 165 // output transition keys (in reverse) 166 for j := len(s.trans) - 1; j >= 0; j-- { 167 err := e.bw.WriteByte(s.trans[j].in) 168 if err != nil { 169 return 0, err 170 } 171 } 172 173 packSize := encodePackSize(transPackSize, outPackSize) 174 err := e.bw.WriteByte(packSize) 175 if err != nil { 176 return 0, err 177 } 178 179 numTrans := encodeNumTrans(len(s.trans)) 180 181 // if number of transitions wont fit in edge header byte 182 // write out separately 183 if numTrans == 0 { 184 if len(s.trans) == 256 { 185 // this wouldn't fit in single byte, but reuse value 1 186 // which would have always fit in the edge header instead 187 err = e.bw.WriteByte(1) 188 if err != nil { 189 return 0, err 190 } 191 } else { 192 err = e.bw.WriteByte(byte(len(s.trans))) 193 if err != nil { 194 return 0, err 195 } 196 } 197 } 198 199 // finally write edge header 200 if s.final { 201 numTrans |= stateFinal 202 } 203 err = e.bw.WriteByte(numTrans) 204 if err != nil { 205 return 0, err 206 } 207 208 return e.bw.counter - 1, nil 209} 210 211func (e *encoderV1) finish(count, rootAddr int) error { 212 footer := make([]byte, footerSizeV1) 213 binary.LittleEndian.PutUint64(footer, uint64(count)) // root addr 214 binary.LittleEndian.PutUint64(footer[8:], uint64(rootAddr)) // root addr 215 n, err := e.bw.Write(footer) 216 if err != nil { 217 return err 218 } 219 if n != footerSizeV1 { 220 return fmt.Errorf("short write of footer %d/%d", n, footerSizeV1) 221 } 222 err = e.bw.Flush() 223 if err != nil { 224 return err 225 } 226 return nil 227} 228