I have written a VB.NET function that takes a byte array, a starting position (in bits), and a number of bits as input. The goal is to remove any occurrences of 3 from the specified range being searched. The function should return the new byte array with the specified length and the information about how many bytes were skipped.
Example: Given the byte array {103, 100, 0, 51, 172, 217, 0, 113, 1, 83, 229, 188, 4, 64, 0, 0, 3, 0, 64, 0, 0, 15, 3, 198, 12, 101, 128}, the starting position (in bits) is 106, and the number of bits is 32. The function should then return {64, 0, 0, 0, 64} (note the skipped 3) and a value of 1. There are 40 bits here, instead of the 32 specified, because the last byte has already started or because the starting position in bits was not aligned to bit position 0. The function should also return the number of skipped bytes so that I can update the position in the bitstream accordingly.
Edge case: If the last read byte is a 3, and it is partially read, it should not be skipped.
The original byte array must not be modified.
I quickly wrote the function a while ago, and it works. However, I am posting this on Code Review to get suggestions to increase the CPU performance.
The use case is parsing specific items in H.264. Occasionally, there are threes between zero-bytes so that the decoder does not confuse the zero-bytes with a new frame (to put it simply).
This is a follow-up question because the response to my previous question already suggested that I should write unit tests and use a separate class as well.
The return tuple must contain a byte[] instead of a List(of Byte), as I will need it later for other functions.
I would like to have this function optimized for performance. Thanks for your input!
I created a test project / minimal compilable example for you:
FormMain.vb (if you need)
Option Strict On
Imports System
Imports System.Collections.Generic
Imports System.Windows.Forms
Friend NotInheritable Class FormMain
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
Dim byteArray As Byte() = New List(Of Byte)() From {103, 100, 0, 51, 172, 217, 0, 113, 1, 83, 229, 188, 4, 64, 0, 0, 3, 0, 64, 0, 0, 15, 3, 198, 12, 101, 128}.ToArray()
Dim result As (Byte(), Integer) = Decoder.ExtractRelevantBytesWithout3(byteArray, 106, 32)
Dim result2 As (Byte(), Integer) = Decoder.ExtractRelevantBytesWithout3(Array.Empty(Of Byte)(), 220, 32)
End Sub
End Class
Class with that method
Option Strict On
Imports System
Imports System.Collections.Generic
Public Class Decoder
Public Shared Function ExtractRelevantBytesWithout3(byteArray As Byte(), bitStartPosition As Integer, bitCount As Integer) As (Byte(), numberOfSkippedBytes As Integer)
If bitStartPosition > byteArray.Length * 8 Then
Throw New ArgumentException("The bit start position exceeds the size of the byte array.", NameOf(bitStartPosition))
End If
Dim result As New List(Of Byte)()
Dim bitsRemaining As Integer = bitCount
Dim currentBitPosition As Integer = bitStartPosition
Dim numberOfSkippedBytes As Integer = 0
Dim increaseOnce As Boolean = True
While bitsRemaining > 0 AndAlso currentBitPosition \ 8 < byteArray.Length
Dim currentByteIndex As Integer = currentBitPosition \ 8
Dim bitIndexWithinByte As Integer = currentBitPosition Mod 8
If bitIndexWithinByte > 0 AndAlso increaseOnce Then
bitsRemaining += 8
increaseOnce = False
End If
Dim currentByte As Byte = byteArray(currentByteIndex)
If currentByte = CByte(3) AndAlso bitsRemaining > 8 Then ' bitsRemaining > 8 means: Do not skip if the 3 is not read completely.
currentBitPosition += 8 ' Skip to the next byte
numberOfSkippedBytes += 1
Continue While
End If
result.Add(currentByte)
currentBitPosition += 8
bitsRemaining -= Math.Min(bitsRemaining, 8) ' Deduct processed bits
End While
Return (result.ToArray(), numberOfSkippedBytes)
End Function
End Class
NUnit tests
using NUnit.Framework;
using System;
using System.Collections.Generic;
namespace ExtractRelevantBytesWithout3.Tests
{
public class Remove3sTest
{
[SetUp]
public void Setup()
{
}
[Test]
public void ByteArrayDoesNotContain3_ReturnsOriginalArray()
{
// Arrange
byte[] originalArray = new List<byte>() { 103, 100, 0, 51, 172, 217, 0, 113, 1, 83, 229, 188, 4, 64, 0, 0, 0, 64, 0, 0, 15, 198, 12, 101, 128 }.ToArray();
// Act
(byte[], int skippedBytes) result = Decoder.ExtractRelevantBytesWithout3(originalArray, bitStartPosition: 106, bitCount: 32);
// Assert
Assert.That(result.Item1, Is.EqualTo(new byte[] { 64, 0, 0, 0, 64 }));
Assert.That(result.skippedBytes, Is.EqualTo(0));
}
[Test]
public void ByteArrayContains3_Removes3()
{
// Arrange
byte[] originalArray = new List<byte>() { 103, 100, 0, 51, 172, 217, 0, 113, 1, 83, 229, 188, 4, 64, 0, 0, 3, 0, 64, 0, 0, 15, 3, 198, 12, 101, 128 }.ToArray();
// Act
(byte[], int skippedBytes) result = Decoder.ExtractRelevantBytesWithout3(originalArray, bitStartPosition: 106, bitCount: 32);
// Assert
Assert.That(result.Item1, Is.EqualTo(new byte[] { 64, 0, 0, 0, 64 }));
Assert.That(result.skippedBytes, Is.EqualTo(1));
}
[Test]
public void ByteArrayContains3_3isPartiallyRead_ReturnsArrayWith3()
{
// Arrange
byte[] originalArray = new List<byte>() { 103, 100, 0, 51, 172, 217, 0, 113, 1, 83, 229, 188, 4, 64, 0, 0, 3, 0, 64, 0, 0, 15, 3, 198, 12, 101, 128 }.ToArray();
// Act
(byte[], int skippedBytes) result = Decoder.ExtractRelevantBytesWithout3(originalArray, bitStartPosition: 146, bitCount: 32);
// Assert
Assert.That(result.Item1, Is.EqualTo(new byte[] { 64, 0, 0, 15, 3 }));
Assert.That(result.skippedBytes, Is.EqualTo(0));
}
/* Edge Cases */
[Test]
public void ByteArrayIsEmpty_ReturnsEmpty()
{
// Arrange
byte[] originalArray = Array.Empty<byte>();
// Act
(byte[], int skippedBytes) result = Decoder.ExtractRelevantBytesWithout3(originalArray, bitStartPosition: 0, bitCount: 1);
// Assert
Assert.That(result.Item1, Is.Empty);
Assert.That(result.skippedBytes, Is.EqualTo(0));
}
[Test]
public void BitPositionGreaterThanArraySize_ThrowsArgumentException()
{
// Arrange
byte[] originalArray = new List<byte>() { 103, 100, 0, 51, 172, 217, 0, 113, 1, 83, 229, 188, 4, 64, 0, 0, 3, 0, 64, 0, 0, 15, 3, 198, 12, 101, 128 }.ToArray();
// Act & Assert
Assert.Throws<ArgumentException>(() =>
Decoder.ExtractRelevantBytesWithout3(originalArray, bitStartPosition: 217, bitCount: 32));
}
[Test]
public void LargeArrayPerformanceTest()
{
// Arrange
byte[] largeArray = new byte[1000000];
for (int i = 0; i < largeArray.Length; i++)
{
largeArray[i] = (byte)(i % 256);
}
// Act
(byte[], int skippedBytes) result = Decoder.ExtractRelevantBytesWithout3(largeArray, bitStartPosition: 0, bitCount: largeArray.Length * 8);
// Assert
Assert.That(result.Item1.Length > 0);
Assert.That(result.skippedBytes, Is.GreaterThan(0));
}
}
}
1 Answer 1
A small improvement is to initialize the list of results by specifying a large enough capacity so that adding bytes doesn't require resizing its internal array.
Lists start with a small array size of 4 and then double the array size if the array gets too small. Resizing the array creates a new array and then copies all the elements from the old array to the new one.
Dim result As New List(Of Byte)(byteArray.Length - bitStartPosition \ 8)
Since currentBitPosition is always increased by 8, bitIndexWithinByte which is set to currentBitPosition Mod 8 will never change. It is used to align the current bit position to full bytes. Since this alignment must be done only once, do it before the While-loop (and get rid of the Boolean variable increaseOnce).
Why carry along the currentBitPosition? All you need inside the loop is the currentByteIndex calculated from it. Do this calculation before the loop as well and directly increase currentByteIndex by 1 instead.
Public Shared Function ExtractRelevantBytesWithout3(byteArray As Byte(), bitStartPosition As Integer, bitCount As Integer) As (Byte(), numberOfSkippedBytes As Integer)
If bitStartPosition > byteArray.Length * 8 Then
Throw New ArgumentException("The bit start position exceeds the size of the byte array.", NameOf(bitStartPosition))
End If
Dim result As New List(Of Byte)(byteArray.Length - bitStartPosition \ 8)
Dim bitsRemaining As Integer = bitCount
Dim currentBitPosition As Integer = bitStartPosition
Dim numberOfSkippedBytes As Integer = 0
Dim bitIndexWithinByte As Integer = currentBitPosition Mod 8
If bitIndexWithinByte > 0 Then
bitsRemaining += 8
End If
Dim currentByteIndex As Integer = currentBitPosition \ 8
While bitsRemaining > 0 AndAlso currentByteIndex < byteArray.Length
Dim currentByte As Byte = byteArray(currentByteIndex)
If currentByte = CByte(3) AndAlso bitsRemaining > 8 Then ' bitsRemaining > 8 means: Do not skip if the 3 is not read completely.
currentByteIndex += 1 ' Skip to the next byte
numberOfSkippedBytes += 1
Continue While
End If
result.Add(currentByte)
currentByteIndex += 1
bitsRemaining -= Math.Min(bitsRemaining, 8) ' Deduct processed bits
End While
Return (result.ToArray(), numberOfSkippedBytes)
End Function
The work within the loop has been reduced and the unit tests are still running.
I would not be astonished if converting this code to C# would improve speed even more. If you need it in a VB project, you can create a C# Library project (a DLL) and add a project reference in the VB app.
The compiler (especially C#), library, JIT and CLR teams are investing an immense effort in performance improvements in every .NET version. Use the newest .NET version available.