Click here to Skip to main content
15,868,016 members
Articles / Programming Languages / SQL
Tip/Trick

Encode / Decode n-bit Integers into byte[]

Rate me:
Please Sign up or sign in to vote.
4.00/5 (2 votes)
1 May 2014CPOL 13.5K   4   1
The class allows you to encode / decode 4, 9 or 17 bit (for example, 1 through 31 bit unsigned int supported) integers to and from a byte[].

Introduction

A pain to write, and my Google-fu was not strong enough to find someone who'd done it for me.

The class allows you to encode / decode 4, 9 or 17 bit (for example) integers to and from a byte[]. I needed it to store some binary keys in a database that are made up of multiple keys, in my case the difference between a byte[] storing 9 bit integers and one storing 16/32 bit integers would be very costly. If you are doing something similar in MSSQL, watch out for 0 byte right truncation (reserve the value of 0 perhaps).

This version of the code supports 1 though 31 bit unsigned integers, it could easily be extended beyond this if needed.

Using the Code

Use freely, keep attributions, no warranty as to usefulness or safety/reliability of the code of course.

C#
using System;
 
namespace MhanoHarkness
{
    /// <summary>
    /// Encode and decode n (1..31) bit integers to / from byte arrays.
    /// 
    /// Converts and array of integers into a byte[] encoded to a 
    /// specific number of bits per integer. Useful when every bit of
    /// storage matters, for example storing a series  of 9 bit integers 
    /// as a byte[] instead of 16 or 32 bit ints could halve or more the 
    /// size of a database in some special cases!
    /// 
    /// Written by Mhano Harkness, special mention to Tim for some 
    /// great help :-)
    /// </summary>
    public class BitIntConverter
    {
        /// <summary>
        /// May return more ints than the number encoded due to padding.
        /// You should reserve the value of 0 to cater for detecting this.
        /// </summary>
        /// <param name="data">byte array encoded by GetBytesFromInts</param>
        /// <param name="bitsPerInt"># used per integer when encoding with
        ///                          GetBytesFromInts</param>
        /// <returns></returns>
        public static int[] GetIntsFromBits(byte[] data, int bitsPerInt)
        {
            if (bitsPerInt < 1 || bitsPerInt > 31)
            {
                throw new ArgumentOutOfRangeException("bitsPerInt", 
                    "1..31 bit unsigned integers supported only.");
            }
 
            var result = new int[(data.Length * 8) / bitsPerInt];
 
            for (var i = 0; i < result.Length; i++)
            {
                var startBit = i * bitsPerInt;
                var startByte = (startBit / 8);
                var endBit = (startBit + bitsPerInt);
                var endByte = (endBit-1) / 8;
                var byteRange = endByte - startByte;
 
                for (var b = 0; b <= byteRange; b++)
                {
                    var bi = startByte + b;
                    Int64 byteAsI64 = data[bi];
                    var amountToShift = (b*8) - (startBit%8);
                    var shiftedForMerge = amountToShift < 0 ? 
                byteAsI64 >> (0 - amountToShift) :
                byteAsI64 << amountToShift;
                    result[i] |= (int)shiftedForMerge;
                }
 
                result[i] &= (1 << bitsPerInt) - 1;
            }
 
            return result;
        }
 
        /// <summary>
        /// Encodes integers into a byte array. Due to padding if 
        /// encoding integers of less than 8 bits you could reserve 0 
        /// as a special case to allow for detecting surplus results
        /// (or explicitly externally keep track of the expected length
        /// and truncate the excess 0 value integers returned by this 
        /// method).
        /// </summary>
        /// <param name="ints">integer arrays, value of each must be >=0
        ///                    and below the maximum storable in an 
        ///                    unsigned int of bitsPerInt bits</param>
        /// <param name="bitsPerInt"># bits to use to encode each
        ///                          integer</param>
        /// <returns></returns>
        public static byte[] GetBytesFromInts(int[] ints, int bitsPerInt)
        {
            if (bitsPerInt < 1 || bitsPerInt > 31)
            {
                throw new ArgumentOutOfRangeException("bitsPerInt", 
                    "1..31 bit unsigned integers supported only.");
            }
            foreach (var i in ints)
            {
                if (i < 0 || i > (Math.Pow(2, bitsPerInt) - 1))
                {
                    throw new ArgumentOutOfRangeException("ints", 
                                  "Integer is <0 or >((2^bitsPerInt)-1)");
                }
            }
 
            var totalBits = (bitsPerInt * ints.Length);
            var result = new byte[(totalBits / 8) + (totalBits % 8 == 0 ? 0 : 1)];
 
            for (var i = 0; i < ints.Length; i++)
            {
                var startBit = i * bitsPerInt;
                var startByte = (startBit/8);
                var endBit = (startBit + bitsPerInt);
                var endByte = endBit / 8 + (endBit % 8 ==0 ? 0 : 1);
                var byteRange = endByte - startByte;
 
                for (var b = 0; b<byteRange; b++)
                {
                    var bi = startByte + b;
                    Int64 asi64 = ints[i];
                    var shiftedForMerge = b == 0 ?
                (asi64 << (startBit % 8)) :
                (asi64 >> ((b * 8) - (startBit % 8)));
                    result[bi] |= (byte)shiftedForMerge;
                }
            }
 
            return result;
        }
    }
}

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Architect
Australia Australia
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionRounding up Pin
bling2-May-14 5:01
bling2-May-14 5:01 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.