Compression, BigEndian and LittleEndian, Bits

In Programming, you can come across a definition called big-endian and little-endian. Today we will talk about these definitions and using with compressing.

Completly, It will custom compression algorithm. Cannot be use in general process but, maybe you can use this algorithm in your process such as socket package, log file.

Now, let’s talk about the definitions of little-endian and big-endian. Little-endian and big-endian are related to data storage formats and refer to how the bytes of a number are organised in memory or communication. These concepts are often important in low-level programming, networking and data protocols.

Compression, BigEndian and LittleEndian, Bits

In a little-endian system, the least significant byte of a multi-byte value (the least significant byte) is stored first in memory. For example, 0x12345678, a 4-byte number, is stored in memory as follows:

78 56 34 12

This method is common on many modern hardware, such as Intel processors. The advantage of little-endian is that it is faster when accessing small bytes because the smallest byte is located at the beginning of memory.

In a big-endian system, the byte with the highest value (the most significant byte) of a multi-byte value is stored first in memory. The same number 0x12345678 is stored as follows in big-endian system:

12 34 56 78

The big-endian scheme is sometimes preferred because it is closer to the human way of reading numbers and is common in networking protocols. For example, the TCP/IP protocol uses a big-endian format.

The difference between these two orders is important when transferring data or storing data in memory. For example, when you send data from one system to another, if the systems use different endian, you may need to perform a conversion to interpret the data correctly.

What is the relationship between compression and these definitions?

To understand the relationship, it is necessary to discuss the Low and High bit.

• Low and High bits means dividing the bits of a number into smaller parts.

• Low bits: Refers to the lowest valued bits of a number (for example, the lowest 16 bits of a u32 number).

• High bits: Refers to the highest-valued bits of the same number (for example, the highest 16 bits of a u32 number).

For example, the low and high bits of the 32-bit number 0x12345678 can be broken down as follows:

• High bits: 0x1234

• Low bits: 0x5678

• Endianness (Little-endian/Big-endian) defines the order in which data is stored in memory or during communication. This is especially important when transferring data between different computer architectures and network protocols.

• Low and High bits are the way we break down and process the data. It is used to perform a specific operation by taking the lowest and highest bits of the number separately or to reduce data loss during compression.

The two are different concepts, but they may need to be considered together when storing and transferring data, because the ordering of data in memory depends on endianness and this can affect low/high bit based operations.

Now let’s do compression with a simple example.

//Let's make a simple StockPrice struct.
struct StockPrice {
    double price;
    uint64_t volume; 
};

Step 1: Simple Compression

In this step we use a simple method that compresses and decompresses the StockPrice structure:

std::vector<uint8_t> compressStockPriceSimple(const StockPrice& stock) {
    std::vector<uint8_t> buffer;

    // Store the price as a double (8 bytes)
    uint64_t price_bits = *reinterpret_cast<const uint64_t*>(&stock.price);
    for (int i = 0; i < 8; ++i) {
        buffer.push_back(price_bits & 0xFF);
        price_bits >>= 8;
    }

    // Store the volume as a uint64_t (8 bytes)
    uint64_t volume = stock.volume;
    for (int i = 0; i < 8; ++i) {
        buffer.push_back(volume & 0xFF);
        volume >>= 8;
    }

    return buffer;
}

StockPrice decompressStockPriceSimple(const std::vector<uint8_t>& data) {
    size_t index = 0;

    // Read the price as a double
    uint64_t price_bits = 0;
    for (int i = 0; i < 8; ++i) {
        price_bits |= static_cast<uint64_t>(data[index++]) << (8 * i);
    }
    double price = *reinterpret_cast<double*>(&price_bits);

    // Read the volume as a uint64_t
    uint64_t volume = 0;
    for (int i = 0; i < 8; ++i) {
        volume |= static_cast<uint64_t>(data[index++]) << (8 * i);
    }

    return {price, volume};
}

2. Improving Compression (Using u8, u16, u32)

In this step, we ensure that the data is stored as u8, u16 or u32 according to its value. For larger data, we continue as u64.

std::vector<uint8_t> compressStockPriceOptimized(const StockPrice& stock) {
    std::vector<uint8_t> buffer;

    // Compress price
    if (stock.price < 256.0) {
        buffer.push_back(0b00); // 00 -> stored as u8
        buffer.push_back(static_cast<uint8_t>(stock.price));
    } else if (stock.price < 65536.0) {
        buffer.push_back(0b01); // 01 -> stored as u16
        uint16_t price_u16 = static_cast<uint16_t>(stock.price);
        buffer.push_back(price_u16 & 0xFF);
        buffer.push_back(price_u16 >> 8);
    } else {
        buffer.push_back(0b10); // 10 -> stored as u32
        uint32_t scaled_price = static_cast<uint32_t>(stock.price * 100.0);
        for (int i = 0; i < 4; ++i) {
            buffer.push_back(scaled_price & 0xFF);
            scaled_price >>= 8;
        }
    }

    // Compress volume (same logic)
    if (stock.volume < 256) {
        buffer.push_back(0b00); // 00 -> stored as u8
        buffer.push_back(static_cast<uint8_t>(stock.volume));
    } else if (stock.volume < 65536) {
        buffer.push_back(0b01); // 01 -> stored as u16
        uint16_t volume_u16 = static_cast<uint16_t>(stock.volume);
        buffer.push_back(volume_u16 & 0xFF);
        buffer.push_back(volume_u16 >> 8);
    } else {
        buffer.push_back(0b10); // 10 -> stored as u32
        uint32_t volume_u32 = static_cast<uint32_t>(stock.volume);
        for (int i = 0; i < 4; ++i) {
            buffer.push_back(volume_u32 & 0xFF);
            volume_u32 >>= 8;
        }
    }

    return buffer;
}

StockPrice decompressStockPriceOptimized(const std::vector<uint8_t>& data) {
    size_t index = 0;

    // Decompress price
    uint8_t price_type = data[index++];
    double price = 0.0;

    switch (price_type) {
        case 0b00:
            price = static_cast<double>(data[index++]);
            break;
        case 0b01: {
            uint16_t price_u16 = data[index++] | (data[index++] << 8);
            price = static_cast<double>(price_u16);
            break;
        }
        case 0b10: {
            uint32_t scaled_price = 0;
            for (int i = 0; i < 4; ++i) {
                scaled_price |= static_cast<uint32_t>(data[index++]) << (8 * i);
            }
            price = static_cast<double>(scaled_price) / 100.0;
            break;
        }
    }

    // Decompress volume (same logic)
    uint8_t volume_type = data[index++];
    uint64_t volume = 0;

    switch (volume_type) {
        case 0b00:
            volume = data[index++];
            break;
        case 0b01:
            volume = data[index++] | (data[index++] << 8);
            break;
        case 0b10: {
            uint32_t volume_u32 = 0;
            for (int i = 0; i < 4; ++i) {
                volume_u32 |= static_cast<uint32_t>(data[index++]) << (8 * i);
            }
            volume = volume_u32;
            break;
        }
    }

    return {price, volume};
}

• price and volume are stored as u8 or u16 for small values.
• For large values they are stored as u32.
• Compression reduces the data size and makes efficient use of memory.

3. Using Low and High Bits

In this step, we further optimise the compression by splitting the u32 values into 16-bit high and low bits.

#include <iostream>
#include <vector>
#include <cstdint>
#include <cmath>

struct StockPrice {
    double price;
    uint64_t volume;
};

std::vector<uint8_t> compressStockPriceWithBits(const StockPrice& stock) {
    std::vector<uint8_t> buffer;

    // Compress price
    if (stock.price < 256.0) {
        buffer.push_back(0b00); // 00 -> stored as u8
        buffer.push_back(static_cast<uint8_t>(stock.price));
    } else if (stock.price < 65536.0) {
        buffer.push_back(0b01); // 01 -> stored as u16
        uint16_t price_u16 = static_cast<uint16_t>(stock.price);
        buffer.push_back(price_u16 & 0xFF);
        buffer.push_back(price_u16 >> 8);
    } else {
        uint32_t scaled_price = static_cast<uint32_t>(stock.price * 100.0);
        uint16_t high_bits = scaled_price >> 16;
        uint16_t low_bits = scaled_price & 0xFFFF;

        if (high_bits == 0) {
            buffer.push_back(0b10); // 10 -> low bits only
            buffer.push_back(low_bits & 0xFF);
            buffer.push_back(low_bits >> 8);
        } else {
            buffer.push_back(0b11); // 11 -> high and low bits
            buffer.push_back(high_bits & 0xFF);
            buffer.push_back(high_bits >> 8);
            buffer.push_back(low_bits & 0xFF);
            buffer.push_back(low_bits >> 8);
        }
    }

    // Compress volume (similar logic)
    if (stock.volume < 256) {
        buffer.push_back(0b00); // 00 -> stored as u8
        buffer.push_back(static_cast<uint8_t>(stock.volume));
    } else if (stock.volume < 65536) {
        buffer.push_back(0b01); // 01 -> stored as u16
        uint16_t volume_u16 = static_cast<uint16_t>(stock.volume);
        buffer.push_back(volume_u16 & 0xFF);
        buffer.push_back(volume_u16 >> 8);
    } else {
        uint32_t volume_u32 = static_cast<uint32_t>(stock.volume);
        uint16_t high_bits = volume_u32 >> 16;
        uint16_t low_bits = volume_u32 & 0xFFFF;

        if (high_bits == 0) {
            buffer.push_back(0b10); // Low bits only
            buffer.push_back(low_bits & 0xFF);
            buffer.push_back(low_bits >> 8);
        } else {
            buffer.push_back(0b11); // High and low bits
            buffer.push_back(high_bits & 0xFF);
            buffer.push_back(high_bits >> 8);
            buffer.push_back(low_bits & 0xFF);
            buffer.push_back(low_bits >> 8);
        }
    }

    return buffer;
}

StockPrice decompressStockPriceWithBits(const std::vector<uint8_t>& data) {
    size_t index = 0;

    // Decompress price
    uint8_t price_type = data[index++];
    double price = 0.0;

    switch (price_type) {
        case 0b00:
            price = static_cast<double>(data[index++]);
            break;
        case 0b01: {
            uint16_t price_u16 = data[index++] | (data[index++] << 8);
            price = static_cast<double>(price_u16);
            break;
        }
        case 0b10: {
            uint16_t low_bits = data[index++] | (data[index++] << 8);
            price = static_cast<double>(low_bits) / 100.0;
            break;
        }
        case 0b11: {
            uint16_t high_bits = data[index++] | (data[index++] << 8);
            uint16_t low_bits = data[index++] | (data[index++] << 8);
            uint32_t scaled_price = (static_cast<uint32_t>(high_bits) << 16) | low_bits;
            price = static_cast<double>(scaled_price) / 100.0;
            break;
        }
    }

    // Decompress volume (similar logic)
    uint8_t volume_type = data[index++];
    uint64_t volume = 0;

    switch (volume_type) {
        case 0b00:
            volume = data[index++];
            break;
        case 0b01:
            volume = data[index++] | (data[index++] << 8);
            break;
        case 0b10: {
            uint16_t low_bits = data[index++] | (data[index++] << 8);
            volume = static_cast<uint64_t>(low_bits);
            break;
        }
        case 0b11: {
            uint16_t high_bits = data[index++] | (data[index++] << 8);
            uint16_t low_bits = data[index++] | (data[index++] << 8);
            volume = (static_cast<uint64_t>(high_bits) << 16) | low_bits;
            break;
        }
    }

    return {price, volume};
}

• If the price and volume values fit in u32, they are stored more efficiently over the high and low bits.
• This method also compresses large values into smaller chunks.

I hope it has been an explanatory and useful article on Little-endian, Bit-endian and Bits.

Happy coding!