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