CODEWITHSUNDEEP
c#arrays
JGU
JGU

Reputation: 899

C# Fastest way to increment a byte array used as an integer counter?

I am using a segmented integer counter (byte array) in a parallel CTR implementation (encryption). The counter needs to be incremented in sizes corresponding to the blocks of data being processed by each processor. So, the number needs to be incremented by more than a single bit value. In other words.. the byte array is acting as a Big Integer, and I need to increase the sum value of the byte array by an integer factor. I am currently using the methods shown below using a while loop, but I am wondering if there is a bit wise method (& | ^ etc), as using a loop seems very wasteful.. any ideas?

private void Increment(byte[] Counter)
{
    int j = Counter.Length;
    while (--j >= 0 && ++Counter[j] == 0) { }
}

/// <summary>
/// Increase a byte array by a numerical value
/// </summary>
/// <param name="Counter">Original byte array</param>
/// <param name="Count">Number to increase by</param>
/// <returns>Array with increased value [byte[]]</returns>
private byte[] Increase(byte[] Counter, Int32 Count)
{
    byte[] buffer = new byte[Counter.Length];

    Buffer.BlockCopy(Counter, 0, buffer, 0, Counter.Length);

    for (int i = 0; i < Count; i++)
        Increment(buffer);

    return buffer;
}

Upvotes: 2

Views: 5034

Answers (2)

JGU
JGU

Reputation: 899

I used a variation of Cory Nelsons answer that creates the array with the correct endian order and returns a new array. This is quite a bit faster then the method first posted.. thanks for the help.

private byte[] Increase(byte[] Counter, int Count)
{
    int carry = 0;
    byte[] buffer = new byte[Counter.Length];
    int offset = buffer.Length - 1;
    byte[] cnt = BitConverter.GetBytes(Count);
    byte osrc, odst, ndst;

    Buffer.BlockCopy(Counter, 0, buffer, 0, Counter.Length);

    for (int i = offset; i > 0; i--)
    {
        odst = buffer[i];
        osrc = offset - i < cnt.Length ? cnt[offset - i] : (byte)0;
        ndst = (byte)(odst + osrc + carry);
        carry = ndst < odst ? 1 : 0;
        buffer[i] = ndst;
    }

    return buffer;
}

Upvotes: 1

Cory Nelson
Cory Nelson

Reputation: 29981

The standard O(n) multi-precision add goes like this (assuming [0] is LSB):

static void Add(byte[] dst, byte[] src)
{
    int carry = 0;

    for (int i = 0; i < dst.Length; ++i)
    {
        byte odst = dst[i];
        byte osrc = i < src.Length ? src[i] : (byte)0;

        byte ndst = (byte)(odst + osrc + carry);

        dst[i] = ndst;
        carry = ndst < odst ? 1 : 0;
    }
}

It can help to think of this is terms of grade-school arithmetic, which is really all it is:

  129
+ 123
-----

Remember, where you'd perform an add and carry for each digit, starting from the left (the least-significant digit)? In this case, each digit is a byte in your array.

Rather than roll your own, have you considered using the arbitrary-precision BigInteger? It was actually created specifically for .NET's own crypto stuff.

Upvotes: 3

Related Questions