1343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih/* 2343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih * Copyright (C) 2014 The Android Open Source Project 3343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih * 4343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih * Licensed under the Apache License, Version 2.0 (the "License"); 5343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih * you may not use this file except in compliance with the License. 6343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih * You may obtain a copy of the License at 7343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih * 8343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih * http://www.apache.org/licenses/LICENSE-2.0 9343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih * 10343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih * Unless required by applicable law or agreed to in writing, software 11343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih * distributed under the License is distributed on an "AS IS" BASIS, 12343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih * See the License for the specific language governing permissions and 14343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih * limitations under the License. 15343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih */ 16343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih 17343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih#include <stdint.h> 18343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih 19343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shihnamespace { 20343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih 21343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// Table for Seal's algorithm for Number of Trailing Zeros. Hacker's Delight 22343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// online, Figure 5-18 (http://www.hackersdelight.org/revisions.pdf) 23343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// The entries whose value is -1 are never referenced. 24343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shihint NTZ_TABLE[] = { 25343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih 32, 0, 1, 12, 2, 6, -1, 13, 3, -1, 7, -1, -1, -1, -1, 14, 26343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih 10, 4, -1, -1, 8, -1, -1, 25, -1, -1, -1, -1, -1, 21, 27, 15, 27343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih 31, 11, 5, -1, -1, -1, -1, -1, 9, -1, -1, 24, -1, -1, 20, 26, 28343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih 30, -1, -1, -1, -1, 23, -1, 19, 29, -1, 22, 18, 28, 17, 16, -1 29343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih}; 30343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih 31343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shihint numberOfTrailingZeros32(int32_t i) { 32343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih uint32_t u = (i & -i) * 0x0450FBAF; 33343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih return NTZ_TABLE[(u) >> 26]; 34343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih} 35343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih 36343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shihuint64_t highestOneBit(uint64_t n) { 37343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih n |= (n >> 1); 38343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih n |= (n >> 2); 39343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih n |= (n >> 4); 40343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih n |= (n >> 8); 41343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih n |= (n >> 16); 42343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih n |= (n >> 32); 43343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih return n - (n >> 1); 44343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih} 45343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih 46343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shihuint64_t _powerOf2(uint64_t u) { 47343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih uint64_t powerOf2 = highestOneBit(u); 48343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih return powerOf2 ? powerOf2 : 1; 49343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih} 50343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih 51343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// Based on Long.numberOfTrailingZeros in Long.java 52343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shihint numberOfTrailingZeros(uint64_t u) { 53343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih int32_t low = u; 54343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih return low !=0 ? numberOfTrailingZeros32(low) 55343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih : 32 + numberOfTrailingZeros32((int32_t) (u >> 32)); 56343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih} 57343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih} 58343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih 59343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shihnamespace webm { 60343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih 61343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// Encode the id and/or size of an EBML element bytes by setting a leading length descriptor bit: 62343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// 63343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// 1xxxxxxx - 1-byte values 64343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// 01xxxxxx xxxxxxxx - 65343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// 001xxxxx xxxxxxxx xxxxxxxx - 66343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// 0001xxxx xxxxxxxx xxxxxxxx xxxxxxxx - ... 67343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// 00001xxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx - 68343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// 000001xx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx - 69343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// 0000001x xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx - 70343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// 00000001 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx - 8-byte values 71343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// 72343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// This function uses the least the number of bytes possible. 73343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shihuint64_t encodeUnsigned(uint64_t u) { 74343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih uint64_t powerOf2 = _powerOf2(u); 75343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih if (u + 1 == powerOf2 << 1) 76343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih powerOf2 <<= 1; 77343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih int shiftWidth = (7 + numberOfTrailingZeros(powerOf2)) / 7 * 7; 78343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih long lengthDescriptor = 1 << shiftWidth; 79343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih return lengthDescriptor | u; 80343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih} 81343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih 82343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// Like above but pads the input value with leading zeros up to the specified width. The length 83343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// descriptor is calculated based on width. 84343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shihuint64_t encodeUnsigned(uint64_t u, int width) { 85343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih int shiftWidth = 7 * width; 86343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih uint64_t lengthDescriptor = 1; 87343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih lengthDescriptor <<= shiftWidth; 88343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih return lengthDescriptor | u; 89343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih} 90343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih 91343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// Calculate the length of an EBML coded id or size from its length descriptor. 92343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shihint sizeOf(uint64_t u) { 93343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih uint64_t powerOf2 = _powerOf2(u); 94343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih int unsignedLength = numberOfTrailingZeros(powerOf2) / 8 + 1; 95343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih return unsignedLength; 96343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih} 97343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih 98343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih// Serialize an EBML coded id or size in big-endian order. 99343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shihint serializeCodedUnsigned(uint64_t u, uint8_t* bary) { 100343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih int unsignedLength = sizeOf(u); 101343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih for (int i = unsignedLength - 1; i >= 0; i--) { 102343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih bary[i] = u & 0xff; 103343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih u >>= 8; 104343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih } 105343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih return unsignedLength; 106343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih} 107343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih 108343947abc8b7c126f966fd32a0b18bff6c2cecd1Robert Shih} 109