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 "bytes" 19 "encoding/binary" 20 "fmt" 21 "strconv" 22) 23 24func init() { 25 registerDecoder(versionV1, func(data []byte) decoder { 26 return newDecoderV1(data) 27 }) 28} 29 30type decoderV1 struct { 31 data []byte 32} 33 34func newDecoderV1(data []byte) *decoderV1 { 35 return &decoderV1{ 36 data: data, 37 } 38} 39 40func (d *decoderV1) clear() { 41 d.data = nil 42} 43 44func (d *decoderV1) getRoot() int { 45 if len(d.data) < footerSizeV1 { 46 return noneAddr 47 } 48 footer := d.data[len(d.data)-footerSizeV1:] 49 root := binary.LittleEndian.Uint64(footer[8:]) 50 return int(root) 51} 52 53func (d *decoderV1) getLen() int { 54 if len(d.data) < footerSizeV1 { 55 return 0 56 } 57 footer := d.data[len(d.data)-footerSizeV1:] 58 dlen := binary.LittleEndian.Uint64(footer) 59 return int(dlen) 60} 61 62func (d *decoderV1) reload(data []byte) { 63 d.data = data 64} 65 66func (d *decoderV1) stateAt(addr int, prealloc fstState) (fstState, error) { 67 state, ok := prealloc.(*fstStateV1) 68 if ok && state != nil { 69 *state = fstStateV1{} // clear the struct 70 } else { 71 state = &fstStateV1{} 72 } 73 err := state.at(d.data, addr) 74 if err != nil { 75 return nil, err 76 } 77 return state, nil 78} 79 80type fstStateV1 struct { 81 data []byte 82 top int 83 bottom int 84 numTrans int 85 86 // single trans only 87 singleTransChar byte 88 singleTransNext bool 89 singleTransAddr uint64 90 singleTransOut uint64 91 92 // shared 93 transSize int 94 outSize int 95 96 // multiple trans only 97 final bool 98 transTop int 99 transBottom int 100 destTop int 101 destBottom int 102 outTop int 103 outBottom int 104 outFinal int 105} 106 107func (f *fstStateV1) isEncodedSingle() bool { 108 if f.data[f.top]>>7 > 0 { 109 return true 110 } 111 return false 112} 113 114func (f *fstStateV1) at(data []byte, addr int) error { 115 f.data = data 116 if addr == emptyAddr { 117 return f.atZero() 118 } else if addr == noneAddr { 119 return f.atNone() 120 } 121 if addr > len(data) || addr < 16 { 122 return fmt.Errorf("invalid address %d/%d", addr, len(data)) 123 } 124 f.top = addr 125 f.bottom = addr 126 if f.isEncodedSingle() { 127 return f.atSingle(data, addr) 128 } 129 return f.atMulti(data, addr) 130} 131 132func (f *fstStateV1) atZero() error { 133 f.top = 0 134 f.bottom = 1 135 f.numTrans = 0 136 f.final = true 137 f.outFinal = 0 138 return nil 139} 140 141func (f *fstStateV1) atNone() error { 142 f.top = 0 143 f.bottom = 1 144 f.numTrans = 0 145 f.final = false 146 f.outFinal = 0 147 return nil 148} 149 150func (f *fstStateV1) atSingle(data []byte, addr int) error { 151 // handle single transition case 152 f.numTrans = 1 153 f.singleTransNext = data[f.top]&transitionNext > 0 154 f.singleTransChar = data[f.top] & maxCommon 155 if f.singleTransChar == 0 { 156 f.bottom-- // extra byte for uncommon 157 f.singleTransChar = data[f.bottom] 158 } else { 159 f.singleTransChar = decodeCommon(f.singleTransChar) 160 } 161 if f.singleTransNext { 162 // now we know the bottom, can compute next addr 163 f.singleTransAddr = uint64(f.bottom - 1) 164 f.singleTransOut = 0 165 } else { 166 f.bottom-- // extra byte with pack sizes 167 f.transSize, f.outSize = decodePackSize(data[f.bottom]) 168 f.bottom -= f.transSize // exactly one trans 169 f.singleTransAddr = readPackedUint(data[f.bottom : f.bottom+f.transSize]) 170 if f.outSize > 0 { 171 f.bottom -= f.outSize // exactly one out (could be length 0 though) 172 f.singleTransOut = readPackedUint(data[f.bottom : f.bottom+f.outSize]) 173 } else { 174 f.singleTransOut = 0 175 } 176 // need to wait till we know bottom 177 if f.singleTransAddr != 0 { 178 f.singleTransAddr = uint64(f.bottom) - f.singleTransAddr 179 } 180 } 181 return nil 182} 183 184func (f *fstStateV1) atMulti(data []byte, addr int) error { 185 // handle multiple transitions case 186 f.final = data[f.top]&stateFinal > 0 187 f.numTrans = int(data[f.top] & maxNumTrans) 188 if f.numTrans == 0 { 189 f.bottom-- // extra byte for number of trans 190 f.numTrans = int(data[f.bottom]) 191 if f.numTrans == 1 { 192 // can't really be 1 here, this is special case that means 256 193 f.numTrans = 256 194 } 195 } 196 f.bottom-- // extra byte with pack sizes 197 f.transSize, f.outSize = decodePackSize(data[f.bottom]) 198 199 f.transTop = f.bottom 200 f.bottom -= f.numTrans // one byte for each transition 201 f.transBottom = f.bottom 202 203 f.destTop = f.bottom 204 f.bottom -= f.numTrans * f.transSize 205 f.destBottom = f.bottom 206 207 if f.outSize > 0 { 208 f.outTop = f.bottom 209 f.bottom -= f.numTrans * f.outSize 210 f.outBottom = f.bottom 211 if f.final { 212 f.bottom -= f.outSize 213 f.outFinal = f.bottom 214 } 215 } 216 return nil 217} 218 219func (f *fstStateV1) Address() int { 220 return f.top 221} 222 223func (f *fstStateV1) Final() bool { 224 return f.final 225} 226 227func (f *fstStateV1) FinalOutput() uint64 { 228 if f.final && f.outSize > 0 { 229 return readPackedUint(f.data[f.outFinal : f.outFinal+f.outSize]) 230 } 231 return 0 232} 233 234func (f *fstStateV1) NumTransitions() int { 235 return f.numTrans 236} 237 238func (f *fstStateV1) TransitionAt(i int) byte { 239 if f.isEncodedSingle() { 240 return f.singleTransChar 241 } 242 transitionKeys := f.data[f.transBottom:f.transTop] 243 return transitionKeys[f.numTrans-i-1] 244} 245 246func (f *fstStateV1) TransitionFor(b byte) (int, int, uint64) { 247 if f.isEncodedSingle() { 248 if f.singleTransChar == b { 249 return 0, int(f.singleTransAddr), f.singleTransOut 250 } 251 return -1, noneAddr, 0 252 } 253 transitionKeys := f.data[f.transBottom:f.transTop] 254 pos := bytes.IndexByte(transitionKeys, b) 255 if pos < 0 { 256 return -1, noneAddr, 0 257 } 258 transDests := f.data[f.destBottom:f.destTop] 259 dest := int(readPackedUint(transDests[pos*f.transSize : pos*f.transSize+f.transSize])) 260 if dest > 0 { 261 // convert delta 262 dest = f.bottom - dest 263 } 264 transVals := f.data[f.outBottom:f.outTop] 265 var out uint64 266 if f.outSize > 0 { 267 out = readPackedUint(transVals[pos*f.outSize : pos*f.outSize+f.outSize]) 268 } 269 return f.numTrans - pos - 1, dest, out 270} 271 272func (f *fstStateV1) String() string { 273 rv := "" 274 rv += fmt.Sprintf("State: %d (%#x)", f.top, f.top) 275 if f.final { 276 rv += " final" 277 fout := f.FinalOutput() 278 if fout != 0 { 279 rv += fmt.Sprintf(" (%d)", fout) 280 } 281 } 282 rv += "\n" 283 rv += fmt.Sprintf("Data: % x\n", f.data[f.bottom:f.top+1]) 284 285 for i := 0; i < f.numTrans; i++ { 286 transChar := f.TransitionAt(i) 287 _, transDest, transOut := f.TransitionFor(transChar) 288 rv += fmt.Sprintf(" - %d (%#x) '%s' ---> %d (%#x) with output: %d", transChar, transChar, string(transChar), transDest, transDest, transOut) 289 rv += "\n" 290 } 291 if f.numTrans == 0 { 292 rv += "\n" 293 } 294 return rv 295} 296 297func (f *fstStateV1) DotString(num int) string { 298 rv := "" 299 label := fmt.Sprintf("%d", num) 300 final := "" 301 if f.final { 302 final = ",peripheries=2" 303 } 304 rv += fmt.Sprintf(" %d [label=\"%s\"%s];\n", f.top, label, final) 305 306 for i := 0; i < f.numTrans; i++ { 307 transChar := f.TransitionAt(i) 308 _, transDest, transOut := f.TransitionFor(transChar) 309 out := "" 310 if transOut != 0 { 311 out = fmt.Sprintf("/%d", transOut) 312 } 313 rv += fmt.Sprintf(" %d -> %d [label=\"%s%s\"];\n", f.top, transDest, escapeInput(transChar), out) 314 } 315 316 return rv 317} 318 319func escapeInput(b byte) string { 320 x := strconv.AppendQuoteRune(nil, rune(b)) 321 return string(x[1:(len(x) - 1)]) 322} 323