Zapisywanie dużych plików z użyciem kodów QR - część 1, zarys teoretyczny

Witajcie!

Ostatnio rozważałem możliwość zapisu dużych plików na wielu kodach QR albo tagach NFC. Wymyśliłem sposób, w jaki można to osiągnąć, i chciałbym go tutaj opisać.

Zapewnie każdy z Was zna kody QR - dwuwymiarowe grafiki, które można zeskanować z użyciem telefonu aby odczytać zakodowany w nich tekst. Najczęściej są one wykorzystywane do zapisywania adresów URL (które prowadzą do stron internetowych lub plików), albo krótkich tekstów. Aplikacje odczytujące kody QR często rozpoznają wzory tekstów, aby np. odczytać informacje zakodowane w kodzie QR od razu jako kontakt. Przykładowo tekst zapisany w formie 

WIFI:S:<SSID>;T:<WEP|WPA|nopass>;P:<PASSWORD>;H:<true|false|blank>;;

pozwala odczytać kod QR od razu jako konfigurację połączenia z Wi-fi.

Kody QR (tak samo jak tagi NFC) mają dość małą pojemność. Wg. Wikipedii jest ona następująca (maksymalna ilość symboli dla kolejno liczb, znaków alfanumerycznych, bajtów, Kanji (Azjatycki alfabet)):

Nawet jeżeli teoretycznie jesteśmy w stanie zapisać aż tak dużą ilość informacji w kodzie QR (czystych danych binarnych możemy w końcu zapisać prawie aż 3 kilobajty), taki kod staje się praktycznie nieużywalny. Jego rozmiar i gęstość danych uniemożliwiają skuteczne zeskanowanie takiego kodu, przynajmniej z użyciem telefonu (co jest moim celem).

Wymyśliłem sposób zapisu danych, który umożliwiłby zapisywanie plików dowolnego rozmiaru z użyciem wielu kodów QR. Ta metoda praktycznie pozwala podzielić dowolny plik na łańcuchy tekstu równej długości, więc może być stosowana z dowolnym nośnikiem, od wielu kodów QR czy tagów NFC po np. płyty CD i zapisanie ogromnego pliku na kilku dyskach.

Oto proponowany przeze mnie format:

[SHA1][rozszerzenie pliku] [numer kodu QR] [ilość kodów QR] [BASE64 (fragment)]

Kodowanie:

Na początku, plik zostanie przekonwertowany do tekstu w formacie BASE64, czyli zapisu bajtów składających się na informację w tekst. Następnie, zostanie wygenerowana unikalna suma kontrolna z tego BASE64, z wykorzystaniem algorytmu SHA1 (wybieram ten ze względu na to, że jest wystarczający do tego zastosowania oraz ma stałą długość wygenerowanej sumy kontrolnej: 40 znaków). W kolejnym kroku, BASE64 zostanie podzielony na fragmenty o takiej długości, aby łącznie z początkiem zapisu nie przekraczał maksymalnej ilości znaków ustalonej na początku wykonania algorytmu. Można wtedy odgórnie przyjąć, że ilość kodów QR będzie najwyżej liczbą czterocyfrową. 

Ostatecznie z tych danych powstanie wiele tekstów w formacie zaproponowanym przeze mnie powyżej, które można zapisać na indywidualnych kodach QR.

Przykładowo powstaną takie teksty:

224d1ec2cc10d7c7fc8032812c9d5fa8c495b7e2PNG 0 30 UG9sc2thIHRvIGty

...

224d1ec2cc10d7c7fc8032812c9d5fa8c495b7e2PNG 30 30 YWogdyBFdXJvcGll

Dekodowanie:

Dekodowanie będzie się odbywać na zasadzie odczytywania wszystkich kodów QR składających się na informację.

Suma kontrolna i rozszerzenie plików pozwalają weryfikować, że kolejne skanowane kody zapisują razem ten sam plik. Rozszerzenie pozwala stwierdzić, jaki rodzaj pliku został zakodowany, a suma kontrolna potwierdzić na końcu procesu, że wszystko odczytano prawidłowo. Przewidywany rozmiar pliku można ocenić mnożąc długość fragmentu BASE64 przez ilość wszystkich kodów. Kody liczymy od zera, ilość wszystkich kodów będzie więc równa ostatniemu indeksowi tablicy, w której będą zapisywane kody QR. Ponieważ suma kontrolna jest zapisana na początku i zawsze będzie miała 40 znaków, nie wymaga ona symbolu separatora w celu wycięcia z odczytanego przez skaner tekstu.

Jeżeli zostaną odczytane wszystkie kody i w każdym suma kontrolna, rozszerzenie oraz ilość kodów będą takie same, można poskładać wszystkie fragmenty BASE64, dokonać ostatecznego sprawdzenia ich integralności poprzez sumę kontrolną i zapisać do pliku wynikowego.

W następnej części przedstawię moją implementację tego rozwiązania. Rozważam także, czy pierwszy kod QR w sekcji na BASE64 nie mógłby zawierać np. ewentualnego opisu pliku. Dla czytelności użyłem w przykładach zapisu spacji jako separatora, ale można wykorzystać inny symbol niewystępujący w BASE64. Takimi symbolami są między innymi $ czy @. Tym samym można na przykład używać znaku $ jako separatora, a jeżeli sekcja na BASE64 w pierwszym kodzie QR (o numerze 0) zacznie się od znaku @ przyjąć, że zawiera on opis pliku i dane pliku zaczynają się od drugiego kodu (o numerze 1). De facto dla każdego kodu można weryfikować poprawność sekcji BASE64 sprawdzając czy nie zawiera ona symboli niewystępujących w tym kodowaniu, ale zwiększyłoby to poziom skomplikowania implementacji oraz jej złożoność obliczeniową z O(n) do O(n^2). Biorąc pod uwagę moc obliczeniową współczesnych urządzeń oraz dość małą ilość przetwarzanego tekstu na każdy odczytany kod QR, nie stanowiłoby to jednak zauważalnej różnicy w wydajności. Poza tym, złożoność obliczeniowa każdego etapu (tworzenie wszystkich tekstów, dekodowanie jednego tekstu, zapisanie ostatecznego pliku po zdekodowaniu) wynosiłaby O(n) (nie uwzględniając implementacji SHA1 i BASE64).

Dziękuję za przeczytanie tego posta. Do zobaczenia w następnych!