include/vlc_bits.h

   1 /*****************************************************************************
   2  * vlc_bits.h : Bit handling helpers
   3  *****************************************************************************
   4  * Copyright (C) 2001, 2002, 2003, 2006, 2015 VLC authors and VideoLAN
   5  * $Id$
   6  *
   7  * Authors: Laurent Aimar <fenrir@via.ecp.fr>
   8  *          Gildas Bazin <gbazin at videolan dot org>
   9  *          Rafaël Carré <funman at videolan dot org>
  10  *
  11  * This program is free software; you can redistribute it and/or modify it
  12  * under the terms of the GNU Lesser General Public License as published by
  13  * the Free Software Foundation; either version 2.1 of the License, or
  14  * (at your option) any later version.
  15  *
  16  * This program is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  19  * GNU Lesser General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU Lesser General Public License
  22  * along with this program; if not, write to the Free Software Foundation,
  23  * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
  24  *****************************************************************************/
  25 #ifndef VLC_BITS_H
  26 #define VLC_BITS_H 1
  27
  28 #include <vlc_common.h>
  29
  30 /**
  31  * \file
  32  * This file defines functions, structures for handling streams of bits in vlc
  33  */
  34
  35 typedef struct bs_s bs_t;
  36
  37 typedef struct
  38 {
  39     /* forward read modifier (p_start, p_end, p_fwpriv, count, pos, remain) */
  40     size_t (*pf_byte_forward)(bs_t *, size_t);
  41     size_t (*pf_byte_pos)(const bs_t *);
  42     size_t (*pf_byte_remain)(const bs_t *);
  43 } bs_byte_callbacks_t;
  44
  45 typedef struct bs_s
  46 {
  47     uint8_t *p_start;
  48     uint8_t *p;         /* points to currently read/written byte */
  49     uint8_t *p_end;
  50
  51     uint8_t  i_left;    /* i_count number of available bits */
  52     bool     b_read_only;
  53
  54     bs_byte_callbacks_t cb;
  55     void    *p_priv;
  56 } bs_t;
  57
  58 static size_t bs_impl_bytes_forward( bs_t *s, size_t i_count )
  59 {
  60     if( s->p == NULL )
  61     {
  62         s->p = s->p_start;
  63         return 1;
  64     }
  65
  66     if( s->p >= s->p_end )
  67         return 0;
  68
  69     if( (size_t) (s->p_end - s->p) < i_count )
  70         i_count = s->p_end - s->p;
  71     s->p += i_count;
  72     return i_count;
  73 }
  74
  75 static size_t bs_impl_bytes_remain( const bs_t *s )
  76 {
  77     if( s->p )
  78         return s->p < s->p_end ? s->p_end - s->p - 1: 0;
  79     else
  80         return s->p_end - s->p_start;
  81 }
  82
  83 static size_t bs_impl_bytes_pos( const bs_t *s )
  84 {
  85     if( s->p )
  86         return s->p < s->p_end ? s->p - s->p_start + 1 : s->p - s->p_start;
  87     else
  88         return 0;
  89 }
  90
  91 static inline void bs_init_custom( bs_t *s, const void *p_data, size_t i_data,
  92                                    const bs_byte_callbacks_t *cb, void *priv )
  93 {
  94     s->p_start = (uint8_t *)p_data;
  95     s->p       = NULL;
  96     s->p_end   = s->p_start + i_data;
  97     s->i_left  = 0;
  98     s->b_read_only = true;
  99     s->p_priv = priv;
 100     s->cb = *cb;
 101 }
 102
 103 static inline void bs_init( bs_t *s, const void *p_data, size_t i_data )
 104 {
 105     bs_byte_callbacks_t cb = {
 106         bs_impl_bytes_forward,
 107         bs_impl_bytes_pos,
 108         bs_impl_bytes_remain,
 109     };
 110     bs_init_custom( s, p_data, i_data, &cb, NULL );
 111 }
 112
 113 static inline void bs_write_init( bs_t *s, void *p_data, size_t i_data )
 114 {
 115     bs_init( s, (const void *) p_data, i_data );
 116     s->b_read_only = false;
 117 }
 118
 119 static inline int bs_refill( bs_t *s )
 120 {
 121     if( s->i_left == 0 )
 122     {
 123        if( s->cb.pf_byte_forward( s, 1 ) != 1 )
 124            return -1;
 125
 126        if( s->p < s->p_end )
 127             s->i_left = 8;
 128     }
 129     return s->i_left > 0 ? 0 : 1;
 130 }
 131
 132 static inline bool bs_eof( bs_t *s )
 133 {
 134     return bs_refill( s ) != 0;
 135 }
 136
 137 static inline size_t bs_pos( const bs_t *s )
 138 {
 139     return 8 * s->cb.pf_byte_pos( s ) - s->i_left;
 140 }
 141
 142 static inline size_t bs_remain( const bs_t *s )
 143 {
 144     return 8 * s->cb.pf_byte_remain( s ) + s->i_left;
 145 }
 146
 147 static inline void bs_skip( bs_t *s, size_t i_count )
 148 {
 149     if( i_count == 0 )
 150         return;
 151
 152     if( bs_refill( s ) )
 153         return;
 154
 155     if( i_count > s->i_left )
 156     {
 157         i_count -= s->i_left;
 158         s->i_left = 0;
 159         if( i_count / 8 )
 160             s->cb.pf_byte_forward( s, i_count / 8 );
 161         i_count = i_count % 8;
 162         if( i_count > 0 && !bs_refill( s ) )
 163             s->i_left = 8 - i_count;
 164     }
 165     else s->i_left -= i_count;
 166 }
 167
 168 static inline uint32_t bs_read( bs_t *s, uint8_t i_count )
 169 {
 170      static const uint32_t i_mask[33] =
 171      {  0x00,
 172         0x01,      0x03,      0x07,      0x0f,
 173         0x1f,      0x3f,      0x7f,      0xff,
 174         0x1ff,     0x3ff,     0x7ff,     0xfff,
 175         0x1fff,    0x3fff,    0x7fff,    0xffff,
 176         0x1ffff,   0x3ffff,   0x7ffff,   0xfffff,
 177         0x1fffff,  0x3fffff,  0x7fffff,  0xffffff,
 178         0x1ffffff, 0x3ffffff, 0x7ffffff, 0xfffffff,
 179         0x1fffffff,0x3fffffff,0x7fffffff,0xffffffff};
 180     uint8_t  i_shr, i_drop = 0;
 181     uint32_t i_result = 0;
 182
 183     if( i_count > 32 )
 184     {
 185         i_drop = i_count - 32;
 186         i_count = 32;
 187     }
 188
 189     while( i_count > 0 )
 190     {
 191         if( bs_refill( s ) )
 192             break;
 193
 194         if( s->i_left > i_count )
 195         {
 196             i_shr = s->i_left - i_count;
 197             /* more in the buffer than requested */
 198             i_result |= ( *s->p >> i_shr )&i_mask[i_count];
 199             s->i_left -= i_count;
 200             break;
 201         }
 202         else
 203         {
 204             i_shr = i_count - s->i_left;
 205             /* less in the buffer than requested */
 206            if( i_shr >= 32 )
 207                i_result = 0;
 208            else
 209                i_result |= (*s->p&i_mask[s->i_left]) << i_shr;
 210            i_count  -= s->i_left;
 211            s->i_left = 0;
 212         }
 213     }
 214
 215     if( i_drop )
 216         bs_skip( s, i_drop );
 217
 218     return( i_result );
 219 }
 220
 221 static inline uint32_t bs_read1( bs_t *s )
 222 {
 223     if( bs_refill( s ) )
 224         return 0;
 225     s->i_left--;
 226     return ( *s->p >> s->i_left )&0x01;
 227 }
 228
 229 static inline void bs_write( bs_t *s, uint8_t i_count, uint32_t i_bits )
 230 {
 231     if( s->b_read_only )
 232         return;
 233
 234     while( i_count > 0 )
 235     {
 236         if( bs_refill( s ) )
 237             break;
 238
 239         i_count--;
 240
 241         if( ( i_bits >> i_count )&0x01 )
 242         {
 243             *s->p |= 1 << ( s->i_left - 1 );
 244         }
 245         else
 246         {
 247             *s->p &= ~( 1 << ( s->i_left - 1 ) );
 248         }
 249         s->i_left--;
 250     }
 251 }
 252
 253 static inline bool bs_aligned( bs_t *s )
 254 {
 255     return s->i_left % 8 == 0;
 256 }
 257
 258 static inline void bs_align( bs_t *s )
 259 {
 260     if( s->i_left % 8 )
 261         s->i_left = 0;
 262 }
 263
 264 static inline void bs_write_align( bs_t *s, uint8_t v )
 265 {
 266     if( !s->b_read_only && (s->i_left % 8) )
 267         bs_write( s, s->i_left, v ? 0xFF : 0 );
 268 }
 269
 270 #define bs_align_0( s ) bs_write_align( s, 0 )
 271 #define bs_align_1( s ) bs_write_align( s, 1 )
 272
 273 /* Read unsigned Exp-Golomb code */
 274 static inline uint_fast32_t bs_read_ue( bs_t * bs )
 275 {
 276     unsigned i = 0;
 277
 278     while( bs_read1( bs ) == 0 && bs->p < bs->p_end && i < 31 )
 279         i++;
 280
 281     return (1U << i) - 1 + bs_read( bs, i );
 282 }
 283
 284 /* Read signed Exp-Golomb code */
 285 static inline int_fast32_t bs_read_se( bs_t *s )
 286 {
 287     uint_fast32_t val = bs_read_ue( s );
 288
 289     return (val & 0x01) ? (int_fast32_t)((val + 1) / 2)
 290                         : -(int_fast32_t)(val / 2);
 291 }
 292
 293 #undef bs_forward
 294
 295 #endif