Diff

To Artifact [5db8094e9b]:

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 ``` ```// Package provides a shifted, reversed fibonacci encoding of bytes // // http://en.wikipedia.org/wiki/Fibonacci_coding maps positive integers as // 1 - 11, 2 - 011, 3 - 0011, 4 - 1011, 5 - 00011 // // Incrementing input bytes by one to allow for zero gives // 0 - 11, 1 - 011, 2 - 0011, 3 - 1011, 4 - 00011 // // The codes are then reversed so that they are easily stored in uints // 0 - 11, 1 - 110, 2 - 1100, 3 - 1101, 4 - 11000 package fibonacci type Numbers []uint64 // Returns the n-th fibonacci number // The result is stored after calculation func (f Numbers) Nth(index int) uint64 { switch { case index <= 1: return 1 case f[index] > 0: break default: f[index] = f.Nth(index-1) + f.Nth(index-2) } return f[index] } // Returns a fibonacci code for an integer as specified in the package doc. func (f Numbers) Code(value uint64) (result uint64) { // Increment to encode zero as one value++ // Find the nearest fibonacci number i := 0 for f.Nth(i+1) <= value { i++ } // Leading bit that signals the start of a fibonacci-encoded integer result |= 1 // Find the Zeckendorf's representation by raising a bit for each // fibonacci number that is less or equal to the difference // between the value and the previous such number for ; i >= 1; i-- { result <<= 1 if f.Nth(i) <= value { result |= 1 value -= f.Nth(i) } } return } // Returns an integer from a fibonacci code as specified in the package doc. func (f Numbers) Decode(value uint64) (result uint64) { i := 1 for (value & 3) != 3 { // Add the fibonacci number for the current bit if it is raised if (value & 1) == 1 { result += f.Nth(i) // We know that the next bit cannot be raised by Zeckendorf's theorem value >>= 2 i += 2 continue } value >>= 1 i++ } result += f.Nth(i) - 1 return } ``` ```| | | | | | | | < < < < | | | | | | > | | ``` ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 ``` ```// Package provides a shifted, reversed fibonacci encoding of unsigned integers. // // http://en.wikipedia.org/wiki/Fibonacci_coding maps positive integers as // 1 - 11, 2 - 011, 3 - 0011, 4 - 1011, 5 - 00011 // // Incrementing input by one to allow for zero gives // 0 - 11, 1 - 011, 2 - 0011, 3 - 1011, 4 - 00011 // // The codes are then reversed so that they are easily stored in uints // 0 - 11, 1 - 110, 2 - 1100, 3 - 1101, 4 - 11000 package fibonacci type Numbers []uint64 // Returns a slice with fibonacci numbers up to the given length func New(size int) Numbers { var fibs Numbers = make(Numbers, size) copy(fibs, []uint64{1, 1}) for i := 2; i < size; i++ { fibs[i] = fibs[i-1] + fibs[i-2] } return fibs } // Returns a fibonacci code for an integer as specified in the package's doc. func (f Numbers) Code(value uint64) (result uint64) { // Increment to encode zero as one value++ // Find the nearest fibonacci number i := 0 for f[i+1] <= value { i++ } // Leading bit that signals the start of a fibonacci-encoded integer result |= 1 // Find the Zeckendorf's representation by raising a bit for each // fibonacci number that is less or equal to the difference // between the value and the previous such number for ; i >= 1; i-- { result <<= 1 if f[i] <= value { result |= 1 value -= f[i] } } return } // Returns an integer from a fibonacci code as specified in the package's doc. func (f Numbers) Decode(value uint64) (result uint64) { i := 1 // Loop until the lowest two bits are both raised for (value & 3) != 3 { // Add the fibonacci number for the current bit if it is raised if (value & 1) == 1 { result += f[i] // We know that the next bit cannot be raised by Zeckendorf's theorem value >>= 2 i += 2 continue } value >>= 1 i++ } result += f[i] - 1 return } ```