1 // Copyright 2017 Google Inc. All rights reserved. 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 15 package s2 16 17 // nthDerivativeCoder provides Nth Derivative Coding. 18 // 19 // (In signal processing disciplines, this is known as N-th Delta Coding.) 20 // 21 // Good for varint coding integer sequences with polynomial trends. 22 // 23 // Instead of coding a sequence of values directly, code its nth-order discrete 24 // derivative. Overflow in integer addition and subtraction makes this a 25 // lossless transform. 26 // 27 // constant linear quadratic 28 // trend trend trend 29 // / \ / \ / \_ 30 // 31 // input |0 0 0 0 1 2 3 4 9 16 25 36 32 // 0th derivative(identity) |0 0 0 0 1 2 3 4 9 16 25 36 33 // 1st derivative(delta coding) | 0 0 0 1 1 1 1 5 7 9 11 34 // 2nd derivative(linear prediction) | 0 0 1 0 0 0 4 2 2 2 35 // 36 // ------------------------------------- 37 // 0 1 2 3 4 5 6 7 8 9 10 11 38 // n in sequence 39 // 40 // Higher-order codings can break even or be detrimental on other sequences. 41 // 42 // random oscillating 43 // / \ / \_ 44 // 45 // input |5 9 6 1 8 8 2 -2 4 -4 6 -6 46 // 0th derivative(identity) |5 9 6 1 8 8 2 -2 4 -4 6 -6 47 // 1st derivative(delta coding) | 4 -3 -5 7 0 -6 -4 6 -8 10 -12 48 // 2nd derivative(linear prediction) | -7 -2 12 -7 -6 2 10 -14 18 -22 49 // 50 // --------------------------------------- 51 // 0 1 2 3 4 5 6 7 8 9 10 11 52 // n in sequence 53 // 54 // Note that the nth derivative isn't available until sequence item n. Earlier 55 // values are coded at lower order. For the above table, read 5 4 -7 -2 12 ... 56 type nthDerivativeCoder struct { 57 n, m int 58 memory [10]int32 59 } 60 61 // newNthDerivativeCoder returns a new coder, where n is the derivative order of the encoder (the N in NthDerivative). 62 // n must be within [0,10]. 63 func newNthDerivativeCoder(n int) *nthDerivativeCoder { 64 c := &nthDerivativeCoder{n: n} 65 if n < 0 || n > len(c.memory) { 66 panic("unsupported n. Must be within [0,10].") 67 } 68 return c 69 } 70 71 func (c *nthDerivativeCoder) encode(k int32) int32 { 72 for i := 0; i < c.m; i++ { 73 delta := k - c.memory[i] 74 c.memory[i] = k 75 k = delta 76 } 77 if c.m < c.n { 78 c.memory[c.m] = k 79 c.m++ 80 } 81 return k 82 } 83 84 func (c *nthDerivativeCoder) decode(k int32) int32 { 85 if c.m < c.n { 86 c.m++ 87 } 88 for i := c.m - 1; i >= 0; i-- { 89 c.memory[i] += k 90 k = c.memory[i] 91 } 92 return k 93 } 94