Als je de grot verlaat en open water bereikt, ontvang je een bericht van de Elfen op het schip.

Het bericht is verzonden met het Buoyancy Interchange Transmission System (BITS), een methode om numerieke uitdrukkingen voor te stellen als een binair datapakket. De computer van je onderzeeër heeft het bericht in hexadecimaal¹ formaat opgeslagen (de invoer van deze opgave).

De eerste stap bij het decoderen van het bericht, is om de hexadecimale voorstelling om te zetten naar een binaire voorstelling. Elk hexadecimaal cijfer komt overeen met vier bits in de binaire voorstelling van het datapakket:

Het BITS-bericht vat één enkel pakket in de buitenste laag die zelf verschillende andere pakketten kan bevatten. De hexadecimale voorstelling van dit pakket kan aan het einde een paar extra 0-bevatten. Deze maken geen deel uit van het bericht en moeten genegeerd worden.

Elk bericht begint met een standaard header: de eerste drie bit coderen de versie van het pakket, en de volgende drie bits coderen de type ID van het pakket. Deze twee waarden zijn getallen en alle getallen die in het pakket gecodeerd zitten worden in binair formaat voorgesteld, met de meest significante bits eerst. Zo stelt een versie die gecodeerd wordt als de binaire reeks 100 bijvoorbeeld het getal 4 voor.

Pakketten met type ID 4 stellen een letterlijke waarde voor. Pakketten met letterlijke waarden coderen één enkel binair getal. Om dit te doen wordt het binair getal opgevuld met voorloopnullen totdat de lengte een veelvoud van vier bits is. Vervolgens wordt het opgedeeld in groepen van vier bits. Elke groep wordt voorafgegaan doot een 1-bit, behalve de laatste groep die voorafgegaan wordt door een 0-bit. Deze groepen van vijf bits volgen onmiddellijk na de header van het pakket. Zo wordt de hexadecimale reeks D2FE28 bijvoorbeeld:

110100101111111000101000
VVVTTTAAAAABBBBBCCCCC

Onder elk bit staat een label die de rol van het bit aangeeft:

De drie bits met label V (110) zijn de versie van het pakket, 6.
De drie bits met label T (100) zijn het type ID van het pakket, 4, wat betekent dat dit pakket een letterlijke waarde voorstelt.
De vijf bits met label A (10111) beginnen met een 1 (niet de laatste groep, lees verder) en bevatten de eerste vier bits van het getal, 0111.
De vijf bits met label B (11110) beginnen met een 1 (niet de laatste groep, lees verder) en bevatten nog vier bits van het getal, 1110.
De vijf bits met label C (00101) beginnen met een 0 (laatste groep, einde van het pakket) en bevatten de laatste vier bits van het getal, 0101.
De drie 0-bits zonder label op het einde zijn extra bits die toegevoegd werden omwille van de hexadecimale voorstelling en moeten genegeerd worden.

Dit pakket stelt dus de letterlijk waarde met binaire voorstelling 011111100101 voor, wat overeenkomt met 2021 in decimale voorstelling.

Elk ander type pakket (elk pakket met een type ID die verschilt van 4) stelt een bewerking voor die één of andere berekening uitvoert op één of meer deelpakketten die erin vervat zitten. Op dit moment zijn de specifieke bewerkingen niet belangrijk, en focussen we ons op het ontleden van de hiërarchie van deelpakketten.

Een bewerkingspakket bevat één of meer deelpakketten. Om aan te geven wat de volgende binaire gegevens zijn die de deelpakketten voorstellen, kan een bewerkingspakket één van twee modi gebruiken. Dit wordt aangegeven door de bit die onmiddellijk volgt op de header van het pakket, en die de lengte-type ID genoemd wordt:

Als de lengte-type ID gelijks is aan 0, dan zijn de volgende 15 bits een getal dat aangeeft wat de totale bit-lengte is van de deelpakketten die in dit pakket vervat zitten.
Als de lengte-type ID gelijk is aan 1, dan zijn de volgende 11 bits een getal dat aangeeft hoeveel deelpakketten er onmiddellijk vervat zitten in dit pakket.

Ten slotte staan na de lengte-type ID en het veld met 15 of 11 bits de deelpakketten die in het pakket vervat zitten.

Dit is bijvoorbeeld een bewerkingspakket (hexadecimale string 38006F45291200) met lengte-type ID 0 die twee deelpakketten bevat:

00111000000000000110111101000101001010010001001000000000
VVVTTTILLLLLLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBBBBBB

De drie bits met label V (001) zijn de versie van het pakket, 1.
De drie bits met label T (110) zijn het type ID van het pakket, 6, wat betekent dat dit pakket een bewerking voorstelt.
Het bit met label I (0) is de lengte-type ID, die aangeeft dat de lengte een getal van 15 bits is die aangeeft wat de totale lengte is van alle deelpakketten die in dit pakket vervat zitten.
De 15 bits met label L (000000000011011) bevatten de bit-lengte van de deelpakketten, 27.
De 11 bits met label A bevatten het eerste deelpakket, een letterlijke waarde die het getal 10 voorstelt.
De 16 bits met label B bevatten het tweede deelpakket, een letterlijke waarde die het getal 20 voorstelt.

Na het verwerken van de 11 en 16 bits aan data voor de deelpakketten, is de totale lengte die aangegeven wordt in L (27) bereikt, en stopt dus het ontleden van dit pakket.

Als een ander voorbeeld is hier een bewerkingspakket (hexadecimale string EE00D40C823060) met lengte-type ID 1 die drie deelpakketten bevat:

11101110000000001101010000001100100000100011000001100000
VVVTTTILLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCC

De drie bits met label V (111) zijn de versie van het pakket, 7.
De drie bits met label T (011) zijn het type ID van het pakket, 3, wat betekent dat dit pakket een bewerking voorstelt.
Het bit met label I (1) is de lengte-type ID, die aangeeft dat de lengte een getal van 11 bits is die aangeeft hoeveel deelpakketten er in dit pakket vervat zitten.
De 11 bits met label L (00000000011) geven aan hoeveel deelpakketten er zijn, 3.
De 11 bits met label A bevatten het eerste deelpakket, een letterlijke waarde die het getal 1 voorstelt.
De 11 bits met label B bevatten het tweede deelpakket, een letterlijke waarde die het getal 2 voorstelt.
De 11 bits met label C bevatten het derde deelpakket, een letterlijke waarde die het getal 3 voorstelt.

Na het verwerken van de drie volledige deelpakketten, is het aantal deelpakketten dat wordt aangegeven in L (3) bereikt, en stopt dus het ontleden van dit pakket.

Voorlopig volstaat het om de hiërarchie van pakketten in het verstuurd bericht te ontleden en de versienummers van alle pakketten op te tellen.

Hier zijn nog een aantal voorbeelden van hexadecimaal gecodeerde berichten:

8A004A801A8002F478 stelt een bewerkingspakket voor (versie 4) dat een bewerkingspakket bevat (versie 1) dat een bewerkingspakket bevat (versie 5) dat een letterlijke waarde bevat (versie 6); dit pakket heeft dus een versie-som van 16.
620080001611562C8802118E34 stelt een bewerkingpakket voor (version 3) met twee deelpakketten; elk deelpakket is een bewerkingspakket die twee letterlijke waarden bevat; dit pakket heeft een versie-som van 12.
C0015000016115A2E0802F182340 heeft dezelfde structuur als het vorige voorbeeld, maar het buitenste pakket gebruikt een andere lengte-type ID; dit pakket heeft een versie-som van 23.
A0016C880162017C3686B18A3D4780 is een bewerkingspakket dat een bewerkingspakket bevat dat een bewerkingspakket bevat die vijf letterlijke waarden bevat; het heeft een versie-som van 31.

Opgave

Decodeer de structuur van een hexadecimaal gecodeerd BITS bericht. Wat krijg je als je de versienummers van alle pakketten bij elkaar optelt? Bepaal dit op de volgende manier:

Schrijf een functie decode waaraan de padnaam (string) moet doorgegeven worden van een tekstbestand met een hexadecimaal gecodeerd BITS bericht. De functie moet de som (number) teruggeven van de versienummers van alle pakketten in het bericht.

Voorbeeld

In deze interactieve sessie gaan we ervan uit dat de tekstbestanden transmission01.txt², transmission02.txt³, transmission03.txt⁴, transmission04.txt⁵ en transmission05.txt⁶ zich in de huidige directory bevinden.

> decode("transmission01.txt")
16
> decode("transmission02.txt")
12
> decode("transmission03.txt")
23
> decode("transmission04.txt")
31
> decode("transmission05.txt")
945