Zajímavé úlohy pro programátory v C a C++ #6

Po půl roce sucha (konečně) přináším další zajímavou programovací úlohu. Tentokrát se jedná o úlohu pro programátory v C++ a na své si přijdou především milovníci bitových manipulací :). A nebojte, nebude to žádná úloha stylu "vytvořte makro pro vzájemné prohození polovin předaného intu".

Zadání

Máte následující neúplné definice dvou šablon:

#include <string>
#include <cassert>
 
using namespace std;
 
template<typename T>
T binaryStringToNumber(const string &binStr) {
    assert(binStr.size() == sizeof(T));
 
    // ?
}
 
template<typename T>
string numberToBinaryString(const T &num) {
    // ?
}

Doplňte těla šablon tak, aby:

• šablona funkce binaryStringToNumber() převedla předaný řetězec na číslo, které je binárně uloženo v tomto řetězci
• a šablona funkce numberToBinaryString() převedla dané číslo na řetězec, který odpovídá binární reprezentaci daného čísla.

Způsob uložení bajtů v paměti (little/big endian) je dán architekturou. Upozorňuji, že dané řetězce musí obsahovat přesnou binární podobu daných čísel bajt po bajtu a naopak, tj. musí platit sizeof(T) == str.size(), kde str je převedený řetězec. Výsledný řetězec tedy nebude textově obsahovat pouze znaky '0' a '1'! Viz příklady v sekci testování.

Omezení a podmínky

• Implementace obou funkcí musí být přenositelná (nespoléhejte na konstrukty s implementačně závislým, nespecifikovaným a nedefinovaným chováním) podle standardu C++98.
• Typový parameter T bude vždy bezznaménkový integrální typ (unsigned char, unsigned short int, unsigned int a unsigned long int).
• Hodnotí se především správnost, srozumitelnost a kvalita kódu z hlediska C++ (takže nepoužívejte věci, co patří do jazyka C, které mají v C++ lepší ekvivalenty, např. místo přetypování stylu jazyka C používejte příslušné operátory static_cast apod.).
• Můžete použít cokoliv ze standardní knihovny jazyka C a C++ (přidejte si příslušné vložení hlavičkových souborů). Kromě nich ale mimo implementace obou šablon nic neměňte!

Testování

Abych vám ulehčil práci, tak zde přikládám ukázku, jak lze dané šablony otestovat. Ukázka není přenositelná a jsou v ní určité předpoklady (na velikost datových typů + architektura používá schéma little endian pro uložení bajtů čísel v paměti), takže si ji budete muset upravit podle své plaformy. Samotné definice šablon ale musí být přenositelné!

#include <climits>
 
int main() {
    assert(CHAR_BIT == 8 && sizeof(short int) == 2 && sizeof(int) == 4 && sizeof(long int) == 8);
 
    // 1B
    assert(binaryStringToNumber<unsigned char>(string("\x00", 1)) == 0x00);
    assert(binaryStringToNumber<unsigned char>(string("\xB8", 1)) == 0xB8);
    assert(binaryStringToNumber<unsigned char>(string("\xFF", 1)) == 0xFF);
    assert(numberToBinaryString<unsigned char>(0x00) == string("\x00", 1));
    assert(numberToBinaryString<unsigned char>(0xC4) == string("\xC4", 1));
    assert(numberToBinaryString<unsigned char>(0xFF) == string("\xFF", 1));
    // 2B
    assert(binaryStringToNumber<unsigned short int>(string("\x00\x00", 2)) == 0x00);
    assert(binaryStringToNumber<unsigned short int>(string("\x28\x51", 2)) == 0x5128);
    assert(binaryStringToNumber<unsigned short int>(string("\xFF\xFF", 2)) == 0xFFFF);
    assert(numberToBinaryString<unsigned short int>(0x00) == string("\x00\x00", 2));
    assert(numberToBinaryString<unsigned short int>(0x2C4B) == string("\x4B\x2C", 2));
    assert(numberToBinaryString<unsigned short int>(0xFFFF) == string("\xFF\xFF", 2));
    // 4B
    assert(binaryStringToNumber<unsigned int>(string("\x28\x7D\xA1\xE8", 4)) == 0xE8A17D28);
    assert(numberToBinaryString<unsigned int>(0x6ABB4C32) == string("\x32\x4C\xBB\x6A", 4));
    // 8B
    assert(binaryStringToNumber<unsigned long int>(string("\x28\x7D\xA1\xE8\xAA\x32\xC4\x99", 8)) == 0x99C432AAE8A17D28UL);
    assert(numberToBinaryString<unsigned long int>(0x3C2103895BF39D0F) == string("\x0F\x9D\xF3\x5B\x89\x03\x21\x3C", 8));
 
    return 0;
}

Řešení

Uvedu celkem dvě řešení - první používá bitové manipulace, druhé na to jde "hrubou silou".

První řešení

#include <limits>
 
template<typename T>
T binaryStringToNumber(const string &binStr) {
    assert(binStr.size() == sizeof(T));
 
    T num = 0;
    num |= binStr[sizeof(T) - 1];
    for (size_t i = 2; i <= sizeof(T); ++i) {
        num <<= CHAR_BIT;
        num |= static_cast<unsigned char>(binStr[sizeof(T) - i]);
    }
 
    return num;
}
 
template<typename T>
string numberToBinaryString(const T &num) {
    string binStr(sizeof(T), '\0');
 
    for (size_t i = 0; i < sizeof(T); ++i) {
        size_t shiftSize = i * CHAR_BIT;
        T byteMask = numeric_limits<unsigned char>::max();
        binStr[i] = (num & (byteMask << shiftSize)) >> shiftSize;
    }
 
    return binStr;
}

Transformace z řetězce na číslo probíhá postupným prováděním bitového součtu (OR) bajtů ze zdrojového řetězce a bajtů z čísla. Po každém provedení bitového součtu dojde k posunutí bitů doleva, aby se vytvořilo místo pro následující bitový součin. Takto dojde k přesné kopii bajt po bajtu. Všimněte si především korektního použití konstanty CHAR_BIT, ve které je uloženo počet bitů v jednom bajtu (potenciálně přenositelnější než použití konstanty 8).

Transformace z čísla na řetězec probíhá tak, že se provede bitový posun bajtu obsahující samé jedničky o příslušný počet bajtů doleva, pak se provede logický součin (AND) s daným číslem (pro vymaskování dané části čísla) a k následnému posunu zpět. Jelikož používáme bezznaménkové typy, tak nás nemusí trápit to, zda operátor bitového posunu doprava zachovává znaménko nebo ne. Opět si povšimněte využití konstanty CHAR_BIT a šablony numeric_limits pro získání maximální možné hodnoty, která se vleze do jednoho bajtu.

Druhé řešení

template<typename T>
T binaryStringToNumber(const string &binStr) {
    assert(binStr.size() == sizeof(T));
 
    T num = 0;
    memcpy(&num, binStr.data(), sizeof(T));
    return num;
}
 
template<typename T>
string numberToBinaryString(const T &num) {
    char tmpBinStr[sizeof(T)] = {};
    memcpy(tmpBinStr, &num, sizeof(T));
    return string(tmpBinStr, sizeof(T));
}

Druhé řešení využívá (s)prostou kopii bajt po bajtu mezi řetězcem a číslem. Možná vás napadlo, že by šlo využít unie (uložit jednu složku a číst z jiné) nebo reinterpret_cast, ale ani jedna z těchto konstrukcí není přenositelná. Použitím memcpy() mě nenapadá žádný důvod, proč by tato implementace neměla být přenositelná.