Lab8

2: Faste mønstre og meta-felter

Det finnes mange ulike typer QR-koder. Den mest fremtredende forskjellen er kanskje dimensjonen til QR-koden, som avgjør hvor mange piksler det er i den. Jo større QR-kode, jo mer informasjon (f. eks. lengre nettadresser) kan den inneholde. I denne oppgaven skal vi for enkelhets skyld begrense oss til å kun jobbe med versjon 2 (QRv2), noe som innebærer at rutenettet vi skal lage er en matrise (2D-liste) med størrelse 25x25.

Matrisen for en QRv2 -kode er delt inn i følgende hovedkomponenter:

• En fast komponent som er lik for alle QRv2 -koder (markert i blått/lyseblått under). Disse feltene hjelper en QR-scanner å finne i hvilken del av bildet QR-koden befinner seg og hvordan den er vinklet og orientert. For oss som ikke er i businessen av å scanne QR-koder men istedet bare produsere dem, er ikke dette noe vi graver oss videre ned i utover at vi selvfølgelig må følge reglene og alltid lage koder som følger dette faste mønsteret.
• En datakomponent som inneholder selve data’en som er lagret (i svart/hvitt under). Dette datafeltet inneholder også underkomponenter for feilretting (error correction), men det kommer vi tilbake til senere.
• En komponent for metadata som sier noe om hvordan datafeltet er «maskert» og hvilket feilrettingsnivå koden benytter seg av i datafeltet (i rødt/rosa under).

I filen qrv2_layout.json (som du allerede har lastet ned til arbeidsmappen din, se introduksjon) finner du en datastruktur som forteller oss hvilke posisjoner i matrisen som hører til den faste komponenten og hvilke verdier de skal ha, samt hvilke posisjoner i matrisen som hører til metadata og hvilke verdier disse posisjonene kan ha ved ulike konfigurasjoner. Ta en kikk på filen den og prøv å forstå hvilken informasjon den inneholder.

En QRv2 -kode kan variere på følgende måter:

• Selve dataen som er lagret i QR-koden kan selvfølgelig variere. Ofte er dette en nettadresse, men det kan i prinsippet være hvilken som helst data. I denne oppgaven begrenser vi oss til å kun jobbe med strenger som data. Nettadresser er en form for streng, så vi vil kunne bruke programmet vårt til å lage QR-koder som fører oss til en nettside.
• Alle QR-koder har en viss kapasitet til å rette opp feil i avlesningen på egen hånd; men hvor stor andel av QR-koden som er feilaktig tolket før lesingen feiler kan variere. Du kan velge mellom fire nivåer av feilretting: L, M, Q og H. Disse ulike nivåene gjør at du kan hente ut korrekt informasjon selv om respektivt 7%, 15%, 25% eller 30% av matrisen blir feiltolket av programmet som leser bildet fra kameraet.
• Alle QR-koder har gått igjennom en prosess som heter «maskering», slik at bildet får en jevn fordeling av svarte og hvite piksler uavhengig av hvilken data bildet representerer. Prosessen innebærer å «flippe» enkelte ruter i matrisen etter et bestemt mønster. Det finnes 8 ulike mønstre man kan velge mellom, og ideelt sett velger vi mønsteret som gir den jevnest mulige fordeling av hvite og svarte ruter.

Når vi oppretter matrisen for QR-koden, gjøres det i fire hovedsteg:

Råversjon	Maskering	Metadata	Faste komponenter

Vi skal nå fokusere på de to siste stegene i denne helheten, nemlig fra vi har en ferdig maskert matrise til vi får en komplett QR-kode. Vi begynner med det siste steget først: å lime inn de faste komponentene. Deretter lager vi en funksjon for å lime inn feltene for metadata.

Begge oppgavene på denne siden skal skrives i filen qr2_matrix_completion.py.

set_fixed_fields

Opprett funksjonen set_fixed_fields som har to parametere

• matrix en kvadratisk matrise (2D-liste), og
• qr_layout et oppslagsverk på samme format du ser i qrv2_layout.json.

Funksjonen skal (destruktivt) endre 2D-listen matrix slik at de faste feltene får riktig verdi i henhold til qr_layout.

def test_set_fixed_fields():
    print('Testing set_fixed_fields...', end='')
    matrix = [
        [1, 0, 1, 0, 1],
        [0, 1, 0, 1, 0],
        [1, 0, 1, 0, 1],
        [0, 1, 0, 1, 0],
        [1, 0, 1, 0, 1],
    ]
    sample_layout = {
        'about': 'A fake and incomplete QR layout for testing only',
        'side_length': 5,
        'fixed_positions': {
            'zeros': [
                [3, 2], [3, 3], [3, 4], [4, 2], [4, 3], [4, 4]
            ],
            'ones': [
                [0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2]
            ]
        }
        # skipping keys 'byte_capacity', 'meta_positions' and 'meta_patterns'
        # since they are irrelevant here 
    }
    set_fixed_fields(matrix, sample_layout)
    assert matrix == [
        [1, 1, 1, 0, 1],
        [1, 1, 1, 1, 0],
        [1, 0, 1, 0, 1],
        [0, 1, 0, 0, 0],
        [1, 0, 0, 0, 0],
    ]

    print(' OK')

set_meta_fields

Metadata-feltet varierer basert på to parametre:

• Feilrettingsnivå (L, M, Q eller H), og
• Maskenummer (angitt ved et tall mellom 0 og 7)

Opprett funksjonen set_meta_fields som har fire parametere:

• matrix en kvadratisk matrise (2D-liste),
• err_corr en streng på ett tegn som indikerer feilrettingsnivå (enten L, M, Q eller H),
• mask_no et tall 0-7 som angir hvilken maske som er benyttet, og
• qr_layout et oppslagsverk på samme format du ser i qrv2_layout.json.

Husk, vi skal ikke gjøre noe med feilrettingskoder eller maskering akkurat nå; vi kan anta at dette allerede er tatt hånd om. Vi skal bare gjøre informasjon om valgene som er gjort tilgjengelig i QR-kodens metafelter.

Funksjonen skal (destruktivt) endre 2D-listen matrix slik at metafeltene får riktig verdi i henhold til qr_layout. Merk at for å vite hvilket mønster som skal brukes, må du slå opp i «meta_patterns» i qr_layout i henhold til parametrene err_corr og mask_no; og for å vite posisjonene hvor dette mønsteret skal plasseres, må du slå opp i «meta_positions». Studer også testen for et forenklet eksempel.

def test_set_meta_fields():
    print('Testing set_meta_fields...', end='')
    # For easier visualization the test uses a matrix of strings rather
    # than 0's and 1's, but ultimately 1's and 0's should also work
    matrix = [
        ['-', '|', '-', '|', '-'],
        ['|', '-', '|', '-', '|'],
        ['-', '|', '-', '|', '-'],
        ['|', '-', '|', '-', '|'],
        ['-', '|', '-', '|', '-'],
    ]
    sample_layout = {
        'about': 'A fake and incomplete QR layout for testing only',
        'side_length': 5,
        # skipping key 'fixed_positions' since it is irrelevant here 
        'meta_positions': {
            'first': [
                [0, 0], [0, 1], [0, 2]
            ],
            'second': [
                [0, 4], [4, 4], [3, 1]
            ]
        },
        'meta_patterns': {
            'L': [
                ['A', 'B', 'C'], # mask_no = 0
                ['a', 'b', 'c']  # mask_no = 1
            ],
            'Q': [
                ['Q', 'R', 'S'], # mask_no = 0
                ['q', 'r', 's']  # mask_no = 1
            ],
        }
    }
    err_corr = 'L'
    mask_no = 0
    set_meta_fields(matrix, err_corr, mask_no, sample_layout)
    assert matrix == [
        ['A', 'B', 'C', '|', 'A'],
        ['|', '-', '|', '-', '|'],
        ['-', '|', '-', '|', '-'],
        ['|', 'C', '|', '-', '|'],
        ['-', '|', '-', '|', 'B'],
    ]

    err_corr = 'Q'
    mask_no = 1
    set_meta_fields(matrix, err_corr, mask_no, sample_layout)
    assert matrix == [
        ['q', 'r', 's', '|', 'q'],
        ['|', '-', '|', '-', '|'],
        ['-', '|', '-', '|', '-'],
        ['|', 's', '|', '-', '|'],
        ['-', '|', '-', '|', 'r'],
    ]

    print(' OK')

Sjekk deg selv

Legg til denne snutten nederst i qr2_matrix_completion.py. Om du har gjort alt rett skal du kunne besøke en nettside med en hyggelig melding når du scanner QR-koden som vises.

if __name__ == '__main__':
    from qr_dummies import sample_masked_matrix
    from qr1_draw import display
    from pathlib import Path
    import json

    # Retrieve sample of premasked matrix without meta/fixed fields
    # and getting the matching config for it.
    matrix, error_correction_level, mask_no = sample_masked_matrix()
    qr_layout = json.loads(Path('qrv2_layout.json').read_text(encoding='utf-8'))

    # Try the functions we have created here
    set_meta_fields(matrix, error_correction_level, mask_no, qr_layout)
    set_fixed_fields(matrix, qr_layout)

    # Draw the picture
    display(matrix)

5: Feilretting

I denne siste delen skal vi se nærmere på hvordan vi skal representere en streng som en liste av bits (1’ere og 0’ere). Du husker kanskje fra kursnotatene om unicode at en streng kan representeres som en sekvens av enere og nullere. Det skal vi ser nærmere på her.

Listen med bits i en QR-kode er delt inn i seks deler:

• Modus er fire bits som forteller hvordan resten av bit-listen skal tolkes. For våre formål skal denne verdien alltid være 0100, som betyr at data’en er lagret som «binær» data; de fleste QR-scannere tolker dette i praksis som at dataen representerer en streng i latin-1 (eller ASCII) enkoding (andre mulige verdier som vi altså ikke skal bruke er: 0001 numerisk modus, 0010 alfanumerisk modus, 1000 japansk kanji, og 0111 ECI-modus).
• Lengde er et tall (i totallsystemet) som indikerer hvor mange bytes dataen består av. Åtte bits utgjør én byte, så vi kan gange tallet med 8 for å finne ut for mange bits som befinner seg i data-seksjonen.
• Data er selve dataen. For våre formål et dette en ASCII-enkodet streng.
• Terminator er fire nuller som følger etter dataen (disse brukes egentlig ikke til noen ting i binærmodus, men må være til stede for å fylle opp plassen).
• Padding er noen faste mønstre som gjentar seg. Hensikten er å bruke opp resten av plassen før feilrettingen begynner. Hvor mye padding det er kommer an på hvor mye data det er og hvor mye plass feilrettingen tar (paddingen kan også være ingenting).
• Feilretting er spesielle bits som gjør det mulig å gjenopprette den originale dataen selv om noen bits av en eller annen grunn har blitt flippet. Denne delen regnes ut på bakgrunn av de foregående delene av bit-listen.

Funksjonene på denne siden skal opprettes i filen qr5_bit_list.py.

string_to_data

Opprett en funksjon string_to_data med én parameter:

• content_string en streng du kan anta består av ASCII -symboler.

Funksjonen skal returnere en liste av bits som representerer strengen i ASCII-enkoding.

def test_string_to_data():
    print('Testing string_to_data...', end='')
    assert [0,1,0,0,0,0,0,1] == string_to_data('A')
    assert [0,1,0,0,0,0,0,1,0,1,0,0,0,0,1,1] == string_to_data('AC')
    foo = [0,1,1,0,0,1,1,0,0,1,1,0,1,1,1,1,0,1,1,0,1,1,1,1]
    assert foo == string_to_data('foo')
    print(' OK')

c = 'A'
bit_list = [int(x) for x in f'{ord(c):08b}'] 

# la 'result' være er en tom liste
# for hvert symbol i content_string:
#    finn bit-listen for symbolet
#    utvid (extend) 'result' med bit-listen
# returner resultatet

get_core_bit_list

Opprett en funksjon get_core_bit_list med én parameter:

• content_string en streng du kan anta består av ASCII -symboler.

Funksjonen skal returnere de fire første delene av en bit-liste: modus, lengde, data og terminator for den gitte strengen

def test_get_core_bit_list():
    print('Testing get_core_bit_list...', end='')
    arg = 'hei'
    expected_head = [0, 1, 0, 0]
    expected_len = [0, 0, 0, 0, 0, 0, 1, 1] # 3 in binary
    expected_data = [int(x) for x in '011010000110010101101001']
    expected_term = [0, 0, 0, 0]
    expected = expected_head + expected_len + expected_data + expected_term

    actual = get_core_bit_list(arg)
    assert expected == actual
    print(' OK')

my_len = 42
len_bit_list = [int(x) for x in f'{my_len:08b}'] 

pad_bit_list

Opprett en funksjon pad_bit_list med to parameter:

• core_bit_list en liste med bits
• pad_to_bytes et tall som sier hvor mange bytes den ferdig paddeded bit-listen skal inneholde

Funksjonen skal destruktivt legge til padding-mønstre på slutten av core_bit_list slik at den til sammen blir pad_to_bytes lang. Husk at én byte er åtte bit, så lengden på den endelige listen skal være 8 * pad_to_bytes.

Paddingen som legges til skal veksle mellom [1, 1, 1, 0, 1, 1, 0, 0] og [0, 0, 0, 1, 0, 0, 0, 1] annenhver gang helt til listen er tilstrekkelig lang.

def test_pad_bit_list():
    print('Testing pad_bit_list...', end='')
    PAD1 = (1, 1, 1, 0, 1, 1, 0, 0)
    PAD2 = (0, 0, 0, 1, 0, 0, 0, 1)
    
    arg = [1, 1, 1, 1, 1, 1, 1, 1]
    expected = arg + list(PAD1) + list(PAD2) + list(PAD1)
    pad_bit_list(arg, 4)
    assert expected == arg

    arg = [1, 1, 1, 1, 1, 1, 1, 1]
    expected = arg + list(PAD1) + list(PAD2) + list(PAD1) + list(PAD2)
    pad_bit_list(arg, 5)
    assert expected == arg

    arg = [1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1]
    expected = arg + list(PAD1) + list(PAD2) + list(PAD1) + list(PAD2)
    pad_bit_list(arg, 6)
    assert expected == arg
    print(' OK')

string_to_bit_list

Opprett en funksjon string_to_bit_list med to parametere:

• content_string, en streng du kan anta består av ASCII -symboler, og
• qr_layout, et oppslagsverk på formatet du finner i qrv2_layout.json.

Funksjonen skal returnere to ting i en tuple:

• en komplett bit-liste, inkludert modus, lengde, data, terminator, padding, og feilretting, og
• en streng på ett tegn: ‘L’, ‘M’, ‘Q’ eller ‘H’ som indikerer hvilket feilrettingsnivå som brukes i bit-listen.

Før vi begynner:

En QRv2-kode har 25x25 piksler, og representerer dermed 625 bit med informasjon. Mye av dette brukes imidlertid til faste komponenter og meta-komponenter, så i praksis er det bare 352 bits (44 bytes) vi har til rådighet (nøkkelen ‘byte_capacity’ i qr_layout forteller oss dette). Denne plassen skal fordeles mellom feltene for modus, lengde, data, terminator, padding og feilrettingskode.

En QR-kode kan ha fire ulike nivåer av feilretting: L, M, Q eller H som gir bedre og bedre nivåer av feilretting. Disse nivåene krever henholdsvis 80, 128, 176 og 224 bits (eller 10, 16, 22 og 28 bytes om du vil). Jo bedre feilretting vi ønsker oss, jo mer plass krever altså feilrettings-komponenten. Konsekvensen av dette er at vi bare kan bruke et høyt nivå av feilretting dersom dataen vi lagrer er tilstrekkelig liten.

Når vi velger nivå av feilretting, gjør vi som følger:

• Vi finner først bit-listen for modus, lengde, data og terminator og ser hvor stor plass dette tar.
• Vi velger deretter nivå av feilretting L, M, Q eller H så høyt som mulig, men slik at det likevel er plass til begge deler (hvis det ikke er plass til laveste feilrettingsnivå, krasj programmet og gi en hensiktsmessig feilmelding).
• Hvis vi ser at det vil bli plass til overs, legger vi til padding før vi regner ut selve feilrettingsmønsteret.

Husk å holde tungen rett i munnen med tanke på bytes og bits. 1 byte = 8 bits.

Forresten, en funksjon for å regne ut selve feilrettingsmønsteret kan du laste ned her: qr6_error_correction.py (du må også installere den eksterne pakken reedsolo. Prøv å skrive python3 -m pip install reedsolo i terminalen eller se notatene om eksterne pakker for eksempler på hvordan man installerer eksterne pakker).

Vil du lære å regne ut feilrettingsmønsteret selv? Sjekk ut INF243.

Ferdigstilling

Gå tilbake til qr0_main.py fra introduksjonssteget og endre importene slik at string_to_bit_list importeres fra qr5_bit_list og ikke fra qr_dummies. Kjør programmet og scan QR-koden som vises. Om du har gjort alt riktig, programmet nå fungerer. Yay!