1// Copyright 2019+ Klaus Post. All rights reserved. 2// License information can be found in the LICENSE file. 3// Based on work by Yann Collet, released under BSD License. 4 5package zstd 6 7import "math/bits" 8 9type seqCoders struct { 10 llEnc, ofEnc, mlEnc *fseEncoder 11 llPrev, ofPrev, mlPrev *fseEncoder 12} 13 14// swap coders with another (block). 15func (s *seqCoders) swap(other *seqCoders) { 16 *s, *other = *other, *s 17} 18 19// setPrev will update the previous encoders to the actually used ones 20// and make sure a fresh one is in the main slot. 21func (s *seqCoders) setPrev(ll, ml, of *fseEncoder) { 22 compareSwap := func(used *fseEncoder, current, prev **fseEncoder) { 23 // We used the new one, more current to history and reuse the previous history 24 if *current == used { 25 *prev, *current = *current, *prev 26 c := *current 27 p := *prev 28 c.reUsed = false 29 p.reUsed = true 30 return 31 } 32 if used == *prev { 33 return 34 } 35 // Ensure we cannot reuse by accident 36 prevEnc := *prev 37 prevEnc.symbolLen = 0 38 return 39 } 40 compareSwap(ll, &s.llEnc, &s.llPrev) 41 compareSwap(ml, &s.mlEnc, &s.mlPrev) 42 compareSwap(of, &s.ofEnc, &s.ofPrev) 43} 44 45func highBit(val uint32) (n uint32) { 46 return uint32(bits.Len32(val) - 1) 47} 48 49var llCodeTable = [64]byte{0, 1, 2, 3, 4, 5, 6, 7, 50 8, 9, 10, 11, 12, 13, 14, 15, 51 16, 16, 17, 17, 18, 18, 19, 19, 52 20, 20, 20, 20, 21, 21, 21, 21, 53 22, 22, 22, 22, 22, 22, 22, 22, 54 23, 23, 23, 23, 23, 23, 23, 23, 55 24, 24, 24, 24, 24, 24, 24, 24, 56 24, 24, 24, 24, 24, 24, 24, 24} 57 58// Up to 6 bits 59const maxLLCode = 35 60 61// llBitsTable translates from ll code to number of bits. 62var llBitsTable = [maxLLCode + 1]byte{ 63 0, 0, 0, 0, 0, 0, 0, 0, 64 0, 0, 0, 0, 0, 0, 0, 0, 65 1, 1, 1, 1, 2, 2, 3, 3, 66 4, 6, 7, 8, 9, 10, 11, 12, 67 13, 14, 15, 16} 68 69// llCode returns the code that represents the literal length requested. 70func llCode(litLength uint32) uint8 { 71 const llDeltaCode = 19 72 if litLength <= 63 { 73 // Compiler insists on bounds check (Go 1.12) 74 return llCodeTable[litLength&63] 75 } 76 return uint8(highBit(litLength)) + llDeltaCode 77} 78 79var mlCodeTable = [128]byte{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 80 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 81 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37, 82 38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39, 83 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 84 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 85 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 86 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42} 87 88// Up to 6 bits 89const maxMLCode = 52 90 91// mlBitsTable translates from ml code to number of bits. 92var mlBitsTable = [maxMLCode + 1]byte{ 93 0, 0, 0, 0, 0, 0, 0, 0, 94 0, 0, 0, 0, 0, 0, 0, 0, 95 0, 0, 0, 0, 0, 0, 0, 0, 96 0, 0, 0, 0, 0, 0, 0, 0, 97 1, 1, 1, 1, 2, 2, 3, 3, 98 4, 4, 5, 7, 8, 9, 10, 11, 99 12, 13, 14, 15, 16} 100 101// note : mlBase = matchLength - MINMATCH; 102// because it's the format it's stored in seqStore->sequences 103func mlCode(mlBase uint32) uint8 { 104 const mlDeltaCode = 36 105 if mlBase <= 127 { 106 // Compiler insists on bounds check (Go 1.12) 107 return mlCodeTable[mlBase&127] 108 } 109 return uint8(highBit(mlBase)) + mlDeltaCode 110} 111 112func ofCode(offset uint32) uint8 { 113 // A valid offset will always be > 0. 114 return uint8(bits.Len32(offset) - 1) 115} 116