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