Josh Coalson | 33abe8c | 2001-03-30 00:44:16 +0000 | [diff] [blame] | 1 | /* libFLAC - Free Lossless Audio Codec library |
Josh Coalson | dea0f5a | 2009-01-07 07:31:28 +0000 | [diff] [blame] | 2 | * Copyright (C) 2001,2002,2003,2004,2005,2006,2007,2008,2009 Josh Coalson |
Josh Coalson | 33abe8c | 2001-03-30 00:44:16 +0000 | [diff] [blame] | 3 | * |
Josh Coalson | afd8107 | 2003-01-31 23:34:56 +0000 | [diff] [blame] | 4 | * Redistribution and use in source and binary forms, with or without |
| 5 | * modification, are permitted provided that the following conditions |
| 6 | * are met: |
Josh Coalson | 33abe8c | 2001-03-30 00:44:16 +0000 | [diff] [blame] | 7 | * |
Josh Coalson | afd8107 | 2003-01-31 23:34:56 +0000 | [diff] [blame] | 8 | * - Redistributions of source code must retain the above copyright |
| 9 | * notice, this list of conditions and the following disclaimer. |
Josh Coalson | 33abe8c | 2001-03-30 00:44:16 +0000 | [diff] [blame] | 10 | * |
Josh Coalson | afd8107 | 2003-01-31 23:34:56 +0000 | [diff] [blame] | 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. |
Josh Coalson | 33abe8c | 2001-03-30 00:44:16 +0000 | [diff] [blame] | 30 | */ |
| 31 | |
Josh Coalson | b1ec796 | 2006-05-24 04:41:36 +0000 | [diff] [blame] | 32 | #if HAVE_CONFIG_H |
| 33 | # include <config.h> |
| 34 | #endif |
| 35 | |
Josh Coalson | 33abe8c | 2001-03-30 00:44:16 +0000 | [diff] [blame] | 36 | #include "private/bitmath.h" |
Josh Coalson | 1b68982 | 2001-05-31 20:11:02 +0000 | [diff] [blame] | 37 | #include "FLAC/assert.h" |
Josh Coalson | 33abe8c | 2001-03-30 00:44:16 +0000 | [diff] [blame] | 38 | |
Josh Coalson | a4e95fc | 2001-07-12 21:28:12 +0000 | [diff] [blame] | 39 | /* An example of what FLAC__bitmath_silog2() computes: |
| 40 | * |
| 41 | * silog2(-10) = 5 |
| 42 | * silog2(- 9) = 5 |
| 43 | * silog2(- 8) = 4 |
| 44 | * silog2(- 7) = 4 |
| 45 | * silog2(- 6) = 4 |
| 46 | * silog2(- 5) = 4 |
| 47 | * silog2(- 4) = 3 |
| 48 | * silog2(- 3) = 3 |
| 49 | * silog2(- 2) = 2 |
| 50 | * silog2(- 1) = 2 |
| 51 | * silog2( 0) = 0 |
| 52 | * silog2( 1) = 2 |
| 53 | * silog2( 2) = 3 |
| 54 | * silog2( 3) = 3 |
| 55 | * silog2( 4) = 4 |
| 56 | * silog2( 5) = 4 |
| 57 | * silog2( 6) = 4 |
| 58 | * silog2( 7) = 4 |
| 59 | * silog2( 8) = 5 |
| 60 | * silog2( 9) = 5 |
| 61 | * silog2( 10) = 5 |
| 62 | */ |
Josh Coalson | 33abe8c | 2001-03-30 00:44:16 +0000 | [diff] [blame] | 63 | unsigned FLAC__bitmath_silog2(int v) |
| 64 | { |
| 65 | while(1) { |
| 66 | if(v == 0) { |
| 67 | return 0; |
| 68 | } |
| 69 | else if(v > 0) { |
| 70 | unsigned l = 0; |
| 71 | while(v) { |
| 72 | l++; |
| 73 | v >>= 1; |
| 74 | } |
| 75 | return l+1; |
| 76 | } |
| 77 | else if(v == -1) { |
| 78 | return 2; |
| 79 | } |
| 80 | else { |
Josh Coalson | 28b1857 | 2002-03-12 16:18:11 +0000 | [diff] [blame] | 81 | v++; |
| 82 | v = -v; |
Josh Coalson | 33abe8c | 2001-03-30 00:44:16 +0000 | [diff] [blame] | 83 | } |
| 84 | } |
| 85 | } |
Josh Coalson | bf26db9 | 2002-10-04 05:24:10 +0000 | [diff] [blame] | 86 | |
| 87 | unsigned FLAC__bitmath_silog2_wide(FLAC__int64 v) |
| 88 | { |
| 89 | while(1) { |
| 90 | if(v == 0) { |
| 91 | return 0; |
| 92 | } |
| 93 | else if(v > 0) { |
| 94 | unsigned l = 0; |
| 95 | while(v) { |
| 96 | l++; |
| 97 | v >>= 1; |
| 98 | } |
| 99 | return l+1; |
| 100 | } |
| 101 | else if(v == -1) { |
| 102 | return 2; |
| 103 | } |
| 104 | else { |
| 105 | v++; |
| 106 | v = -v; |
| 107 | } |
| 108 | } |
| 109 | } |