Catalanforyouforever
Reputation: 33
Index Out of Range error when Huffman Coding
I was trying to encode and decode an image using Huffman codes. I am encountering an issue when calling the methods from this class in the main method:
using System;
using System.Collections.Generic;
using System.Drawing;
using System.IO;
using System.Linq;
public static class VLHuffman
{
public static byte[] ConvertToByteArray(List<bool> boolList)
{
int numBytes = (boolList.Count + 7) / 8;
byte[] byteArray = new byte[numBytes];
for (int i = 0; i < boolList.Count; i++)
{
if (boolList[i])
{
byteArray[i / 8] |= (byte)(1 << (7 - i % 8));
}
}
return byteArray;
}
private const int END_OF_FILE = -1;
private const int MAX_BUFFER_SIZE = 256;
private static int numAlphabets = 256;
private static int numActive = 0;
private static int[] frequency;
private static uint originalSize = 0;
private static List<Node> nodes;
private static int numNodes = 0;
private static int[] leafIndex;
private static int[] parentIndex;
private static int freeIndex = 1;
private static int[] stack;
private static int stackTop;
private static byte[] buffer = new byte[MAX_BUFFER_SIZE];
private static int bitsInBuffer = 0;
private static int currentBit = 0;
private static bool eofInput = false;
public static List<bool> Compress(Bitmap inputImage)
{
List<int> pixelValues = GetImagePixelValues(inputImage);
DetermineFrequency(pixelValues);
stack = new int[numActive - 1];
AllocateTree();
AddLeaves();
BuildTree();
List<bool> compressedData = new List<bool>();
EncodeHeader(compressedData);
foreach (int pixelValue in pixelValues)
{
EncodeAlphabet(compressedData, pixelValue);
}
FlushBuffer(compressedData);
return compressedData;
}
public static Bitmap Decompress(List<bool> compressedData, int width, int height)
{
ReadHeader(compressedData);
BuildTree();
List<int> decompressedPixelValues = DecodeBitStream(compressedData);
return GetImageFromPixelValues(decompressedPixelValues, width, height);
}
private static void DetermineFrequency(List<int> pixelValues)
{
frequency = new int[2 * numAlphabets];
leafIndex = new int[numAlphabets - 1];
foreach (int pixelValue in pixelValues)
{
++frequency[pixelValue];
++originalSize;
}
for (int i = 0; i < numAlphabets; ++i)
{
if (frequency[i] > 0)
++numActive;
}
}
private static void AllocateTree()
{
nodes = new List<Node>(2 * numActive);
parentIndex = new int[numActive];
}
private static int AddNode(int index, int weight)
{
int i = numNodes++;
while (i > 0 && nodes[i - 1].Weight > weight)
{
nodes[i] = nodes[i - 1];
if (nodes[i].Index < 0)
++leafIndex[-nodes[i].Index];
else
++parentIndex[nodes[i].Index];
--i;
}
nodes[i] = new Node(index, (uint)weight);
if (index < 0)
leafIndex[-index] = i;
else
parentIndex[index] = i;
return i;
}
private static void AddLeaves()
{
for (int i = 0; i < numAlphabets; ++i)
{
int freq = frequency[i];
if (freq > 0)
AddNode(-(i + 1), freq);
}
}
private static void BuildTree()
{
int a, b, index;
while (freeIndex < numNodes)
{
a = freeIndex++;
b = freeIndex++;
index = AddNode(b / 2, (int)(nodes[a].Weight + nodes[b].Weight));
parentIndex[b / 2] = index;
}
}
private static List<int> DecodeBitStream(List<bool> compressedData)
{
int i = 0, bit, nodeIndex = nodes[numNodes].Index;
List<int> decompressedPixelValues = new List<int>();
while (true)
{
bit = ReadBit(compressedData);
if (bit == -1)
break;
nodeIndex = nodes[nodeIndex * 2 - bit].Index;
if (nodeIndex < 0)
{
int pixelValue = -nodeIndex - 1;
decompressedPixelValues.Add(pixelValue);
if (++i == originalSize)
break;
nodeIndex = nodes[numNodes].Index;
}
}
return decompressedPixelValues;
}
private static void EncodeAlphabet(List<bool> compressedData, int character)
{
int nodeIndex;
stackTop = 0;
nodeIndex = leafIndex[character + 1];
while (nodeIndex < numNodes)
{
stack[stackTop++] = nodeIndex % 2;
nodeIndex = parentIndex[(nodeIndex + 1) / 2];
}
while (--stackTop > -1)
WriteBit(compressedData, stack[stackTop]);
}
private static void EncodeHeader(List<bool> compressedData)
{
byte[] headerBytes = WriteHeader();
foreach (byte headerByte in headerBytes)
{
for (int i = 7; i >= 0; --i)
{
int bit = (headerByte >> i) & 0x01;
compressedData.Add(bit == 1);
}
}
}
private static byte[] WriteHeader()
{
List<byte> headerBytes = new List<byte>();
int byteCount = sizeof(uint) + 1 + numActive * (1 + sizeof(int));
headerBytes.AddRange(BitConverter.GetBytes(originalSize));
headerBytes.Add((byte)numActive);
for (int i = 1; i <= numActive; ++i)
{
headerBytes.Add((byte)(-nodes[i].Index - 1));
byte[] weightBytes = BitConverter.GetBytes(nodes[i].Weight);
headerBytes.AddRange(weightBytes);
}
return headerBytes.ToArray();
}
private static void ReadHeader(List<bool> compressedData)
{
byte[] headerBytes = ReadBytes(compressedData, sizeof(uint) + 1 + numActive * (1 + sizeof(int)));
using (MemoryStream stream = new MemoryStream(headerBytes))
using (BinaryReader reader = new BinaryReader(stream))
{
originalSize = reader.ReadUInt32();
numActive = reader.ReadByte();
AllocateTree(); // Corrected method name
byte[] buffer = ReadBytes(compressedData, numActive * (1 + sizeof(int)));
int byteIndex = 0;
for (int i = 1; i <= numActive; ++i)
{
nodes[i].Index = -(buffer[byteIndex++] + 1);
nodes[i].Weight = BitConverter.ToUInt32(buffer, byteIndex);
byteIndex += sizeof(int);
}
numNodes = numActive;
}
}
private static byte[] ReadBytes(List<bool> compressedData, int count)
{
List<byte> bytes = new List<byte>();
for (int i = 0; i < count; i += 8)
{
byte currentByte = 0;
for (int j = 7; j >= 0; --j)
{
int bit = ReadBit(compressedData);
currentByte |= (byte)(bit << j);
}
bytes.Add(currentByte);
}
return bytes.ToArray();
}
private static int ReadBit(List<bool> compressedData)
{
if (currentBit == bitsInBuffer)
{
if (eofInput)
return END_OF_FILE;
else
{
int bytesToRead = Math.Min(MAX_BUFFER_SIZE, compressedData.Count - bitsInBuffer / 8);
for (int i = 0; i < bytesToRead; ++i)
{
buffer[i] = Convert.ToByte(compressedData[bitsInBuffer / 8 + i]);
}
bitsInBuffer = bytesToRead * 8;
currentBit = 0;
if (bitsInBuffer == 0)
return END_OF_FILE;
}
}
int bit = (buffer[currentBit / 8] >> (7 - currentBit % 8)) & 0x01;
++currentBit;
return bit;
}
private static void WriteBit(List<bool> compressedData, int bit)
{
if (bitsInBuffer == MAX_BUFFER_SIZE << 3)
{
foreach (var byteValue in buffer.Take(bitsInBuffer / 8))
{
for (int i = 7; i >= 0; i--)
{
bool boolValue = ((byteValue >> i) & 0x01) == 1;
compressedData.Add(boolValue);
}
}
bitsInBuffer = 0;
}
if (bit == 1)
buffer[bitsInBuffer / 8] |= (byte)(0x1 << (7 - bitsInBuffer % 8));
++bitsInBuffer;
}
private static void FlushBuffer(List<bool> compressedData)
{
if (bitsInBuffer > 0)
{
foreach (var byteValue in buffer.Take((bitsInBuffer + 7) / 8))
{
for (int i = 7; i >= 0; i--)
{
bool boolValue = ((byteValue >> i) & 0x01) == 1;
compressedData.Add(boolValue);
}
}
bitsInBuffer = 0;
}
}
private static List<int> GetImagePixelValues(Bitmap inputImage)
{
List<int> pixelValues = new List<int>();
for (int y = 0; y < inputImage.Height; y++)
{
for (int x = 0; x < inputImage.Width; x++)
{
Color pixelColor = inputImage.GetPixel(x, y);
int grayscaleValue = (int)(pixelColor.R * 0.3 + pixelColor.G * 0.59 + pixelColor.B * 0.11);
pixelValues.Add(grayscaleValue);
}
}
return pixelValues;
}
private static Bitmap GetImageFromPixelValues(List<int> pixelValues, int width, int height)
{
Console.WriteLine($"Expected pixel values count: {width * height}");
Bitmap decompressedImage = new Bitmap(width, height);
using (MemoryStream stream = new MemoryStream())
{
using (BinaryWriter binaryWriter = new BinaryWriter(stream))
{
foreach (int pixelValue in pixelValues)
{
binaryWriter.Write((byte)pixelValue);
}
}
stream.Position = 0;
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
int pixelValue = stream.ReadByte();
Color newColor = Color.FromArgb(pixelValue, pixelValue, pixelValue);
decompressedImage.SetPixel(x, y, newColor);
}
}
}
return decompressedImage;
}
private class Node : IComparable<Node>
{
public int Index { get; set; }
public uint Weight { get; set; }
public Node(int index, uint weight)
{
Index = index;
Weight = weight;
}
public int CompareTo(Node other)
{
return Weight.CompareTo(other.Weight);
}
}
}
I have tried at least five different methods of going at Huffman coding. But every time, I am getting an error saying:
Unhandled exception. System.ArgumentOutOfRangeException: Index was out of range. Must be non-negative and less than the size of the collection. (Parameter 'index')
at System.Collections.Generic.List`1.set_Item(Int32 index, T value)
at VLHuffman.AddNode(Int32 index, Int32 weight) in VLHuffman.cs:line 98
at VLHuffman.AddLeaves() in VLHuffman.cs:line 112
at VLHuffman.Compress(Bitmap inputImage) in VLHuffman.cs:line 45
at Program.Main() in Program.cs:line 60
I tried explicitly casting, that didn't work. Somewhere the conversion isn't working.
Upvotes: 0
Views: 41
Answers (1)
woodi
Reputation: 1
The stack trace gives a hint towards the offending statement: nodes[i] = new Node(index, (uint)weight); throws an IndexOutOfRangeException because it is trying to access a list item that doesn't exist.
While early on the nodes-List is initialized with an apropriate capacity, at no point any items are added.
The way the code is written I suppose using an array instead of a list will solve the issue right away (just like leafIndex and parentIndex are just arrays).
Upvotes: 0