1 /* libFLAC - Free Lossless Audio Codec library 2 * Copyright (C) 2001,2002,2003,2004,2005,2006,2007 Josh Coalson 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 8 * - Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 11 * - Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * - Neither the name of the Xiph.org Foundation nor the names of its 16 * contributors may be used to endorse or promote products derived from 17 * this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR 23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 26 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 27 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 28 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 29 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 #if HAVE_CONFIG_H 33 # include <config.h> 34 #endif 35 36 #include "private/bitmath.h" 37 #include "FLAC/assert.h" 38 39 /* An example of what FLAC__bitmath_ilog2() computes: 40 * 41 * ilog2( 0) = assertion failure 42 * ilog2( 1) = 0 43 * ilog2( 2) = 1 44 * ilog2( 3) = 1 45 * ilog2( 4) = 2 46 * ilog2( 5) = 2 47 * ilog2( 6) = 2 48 * ilog2( 7) = 2 49 * ilog2( 8) = 3 50 * ilog2( 9) = 3 51 * ilog2(10) = 3 52 * ilog2(11) = 3 53 * ilog2(12) = 3 54 * ilog2(13) = 3 55 * ilog2(14) = 3 56 * ilog2(15) = 3 57 * ilog2(16) = 4 58 * ilog2(17) = 4 59 * ilog2(18) = 4 60 */ 61 unsigned FLAC__bitmath_ilog2(FLAC__uint32 v) 62 { 63 unsigned l = 0; 64 FLAC__ASSERT(v > 0); 65 while(v >>= 1) 66 l++; 67 return l; 68 } 69 70 unsigned FLAC__bitmath_ilog2_wide(FLAC__uint64 v) 71 { 72 unsigned l = 0; 73 FLAC__ASSERT(v > 0); 74 while(v >>= 1) 75 l++; 76 return l; 77 } 78 79 /* An example of what FLAC__bitmath_silog2() computes: 80 * 81 * silog2(-10) = 5 82 * silog2(- 9) = 5 83 * silog2(- 8) = 4 84 * silog2(- 7) = 4 85 * silog2(- 6) = 4 86 * silog2(- 5) = 4 87 * silog2(- 4) = 3 88 * silog2(- 3) = 3 89 * silog2(- 2) = 2 90 * silog2(- 1) = 2 91 * silog2( 0) = 0 92 * silog2( 1) = 2 93 * silog2( 2) = 3 94 * silog2( 3) = 3 95 * silog2( 4) = 4 96 * silog2( 5) = 4 97 * silog2( 6) = 4 98 * silog2( 7) = 4 99 * silog2( 8) = 5 100 * silog2( 9) = 5 101 * silog2( 10) = 5 102 */ 103 unsigned FLAC__bitmath_silog2(int v) 104 { 105 while(1) { 106 if(v == 0) { 107 return 0; 108 } 109 else if(v > 0) { 110 unsigned l = 0; 111 while(v) { 112 l++; 113 v >>= 1; 114 } 115 return l+1; 116 } 117 else if(v == -1) { 118 return 2; 119 } 120 else { 121 v++; 122 v = -v; 123 } 124 } 125 } 126 127 unsigned FLAC__bitmath_silog2_wide(FLAC__int64 v) 128 { 129 while(1) { 130 if(v == 0) { 131 return 0; 132 } 133 else if(v > 0) { 134 unsigned l = 0; 135 while(v) { 136 l++; 137 v >>= 1; 138 } 139 return l+1; 140 } 141 else if(v == -1) { 142 return 2; 143 } 144 else { 145 v++; 146 v = -v; 147 } 148 } 149 } 150
