Als je veerboot de zeehaven nadert, roept de kapitein je opnieuw ter hulp. Het computersysteem dat de zeehaven beheert, is niet compatibel met het programma dat zorgt voor het automatisch aanmeren. Daardoor worden de parameters voor het aanmeren niet correct geïnitialiseerd in het programmageheugen.

Na een korte inspectie ontdekt je dat het computersysteem van de zeehaven op een vreemde manier gebruikmaakt van bitmasks1 in haar installatieprogramma. Hoewel je niet de juiste decodeerchip bij de hand hebt, kan je die makkelijk softwarematig emuleren!

Het installatieprogramma (de invoer van deze opgave) kan ofwel de bitmask aanpassen of een waarde naar het geheugen schrijven. Waarden en geheugenadressen zijn beide 36-bit unsigned integers. Als we bijvoorbeeld eventjs de bitmask negeren, dan zou een regel met mem[8] = 11 de waarde 11 naar geheugenadres 8 schrijven.

De bitmask wordt altijd gegeven als een string van 36 bits, geschreven met de meest significante bit (die correspondeert met 2^35) aan de linkerkant en de minst significante bit (2^0 ofwel de 1-bit van de eenheden) aan de rechterkant. De huidige bitmask wordt toegepast op de waarden, onmiddellijk voordat ze naar het geheugen geschreven worden: een 0 of 1 overschrijft de corresponderende bit in de waarde, terwijl een X de corresponderende bit in de waarde ongewijzgd laat.

Stel dat we bijvoorbeeld het volgende programma hebben:

mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem[8] = 11
mem[7] = 101
mem[8] = 0

Dit programma begint met het specificeren van de bitmask (mask = ....). De bitmask die ingesteld wordt, overschrijft twee bits in elke geschreven waarde: de 2-bit wordt overschreven met een 0, en de 64-bit wordt overschreven met een 1.

Het programma probeert vervolgens de waarde 11 naar geheugenadres 8 te schrijven. Door alles uit te breiden naar individuele bits, wordt de bitmask als volgt toegepast:

waarde:    000000000000000000000000000000001011  (decimaal 11)
bitmask:   XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
resultaat: 000000000000000000000000000001001001  (decimaal 73)

Vanwege de bitmask wordt in plaats daarvan dus de waarde 73 naar geheugenadres 8 geschreven. Daarna probeert het programma de waarde 101 naar adres 7 te schrijven:

waarde:    000000000000000000000000000001100101  (decimaal 101)
bitmask:   XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
resultaat: 000000000000000000000000000001100101  (decimaal 101)

Deze keer heeft de bitmask geen effect, aangezien de bits die overschreven worden al de waarden hadden die de bitmask probeerde in te stellen. Ten slotte probeert het programma de waarde 0 te schrijven naar adres 8:

waarde:    000000000000000000000000000000000000  (decimaal 0)
bitmask:   XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
resultaat: 000000000000000000000000000001000000  (decimaal 64)

In plaats daarvan wordt de waarde 64 naar adres 8 geschreven, waarbij de waarde wordt overschreven die eerder naar dat adres was geschreven.

Om het aanmeerprogramma van je veerboot te initialiseren, heb je de som van alle waarden nodig die in het geheugen zijn achtergebleven nadat het initialisatieprogramma voltooid is. (Elk adres van de volledige 36-bit adresruimte is initieel ingesteld op de waarde 0.) In het bovenstaande voorbeeld zijn er slechts twee waarden in het geheugen die verschillen van nul — 101 (op adres 7) en 64 (op adres 8) — die als som 165 opleveren.

Opgave

Voer het initialisatieprogramma uit. Wat is de som van alle waarden die in het geheugen zijn achtergebleven nadat het programma voltooid is? Hiervoor ga je als volgt te werk:

Voorbeeld

In deze interactieve sessie gaan we ervan uit dat het tekstbestand program.txt2 zich in de huidige directory bevindt.

> bitmask 11 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X"
73
> bitmask 101 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X"
101
> bitmask 0 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X"
64

> memory "program.txt"
165