/** Relational QR Code Model 2 implementation in pure Prolog. * * Module: * :- use_module(qr). * * Public predicates: * - qr_code/2, qr_code/3, qr_code/4 * - qr_sequence/2, qr_sequence/3, qr_sequence/4 * - qr/1, qr/2, qr/3 * - qr_decode/2, qr_decode/3 * - qr_decode_stdin/1, qr_decode_stdin/2 * - qr_decode_file/2, qr_decode_file/3 * - qr_analysis/2 * - qr_penalty/2, qr_penalty_breakdown/2 * - qr_mask_penalties/3, qr_codewords/4 * - qr_capacity/2, qr_sequence_parity/2 * - qr_version_size/2, qr_grid_size/2, qr_grid_version/2 * - display_qr/1, display_qr_wide/1, qr_render/1 * - qr_spec/1, spec_property/2 * - spec_version/2, spec_level/2, spec_mode/2, spec_mask/2 * - test/0 * * This file is ordered to follow the QR pipeline: * 1. Public relational API * 2. Stream encoding/decoding (segments, bits, codewords) * 3. Matrix encoding/decoding (function patterns, masks, grid) * 4. Reed-Solomon block layout and correction * 5. Low-level helpers and static tables * * Scope kept intentionally small and readable: * - QR Model 2 * - Versions 1 through 40 * - Error correction levels: l, m, q, h * - Modes: numeric, alphanumeric, byte, kanji, and explicit ECI text * - Control segments: ECI, FNC1 first/second position, structured append * - All eight masks * * Example queries: * ?- qr("byakuren"). * ?- qr("A1漢B2", Spec), member(mode(segments), Spec). * ?- spec_property(level(h), Spec), qr("byakuren", Spec). * ?- spec_version(Spec, 1), spec_mask(Spec, 3), qr("byakuren", Spec, Grid). * ?- qr_code("byakuren", Grid, Spec). * ?- qr_code("byakuren", Grid), qr_code(Text, Grid, Spec). * ?- qr_decode_file("byakuren-qr.txt", Data, Spec). * ?- qr_analysis("byakuren", Analysis). * ?- qr_code("byakuren", Grid, [version(1), level(q), mode(byte), mask(M)]), * qr_penalty(Grid, Penalty). * ?- qr_code("byakuren", Grid, [version(1), level(q), mode(byte), mask(7)]), * qr_penalty_breakdown(Grid, Breakdown). * ?- qr_mask_penalties("byakuren", * [version(1), level(q), mode(byte), mask(_)], * Penalties). * ?- qr_code("byakuren", Grid, [version(1), level(q), mode(byte), mask(7)]), * qr_codewords(Grid, * [version(1), level(q), mode(byte), mask(7)], * ReceivedCodewords, * CorrectedCodewords). * ?- qr_sequence("byakuren", Grids, Specs). * ?- qr_sequence("A1漢B2", Grids, Specs, Stages). * ?- qr_capacity([version(1), level(q), mode(_), mask(_)], Capacity). * ?- qr_sequence_parity("byakuren", Parity). * ?- qr_version_size(7, Size). * ?- qr_code(qr_data([fnc1(first), byte("bya"), byte("kuren")]), Grid, Spec). * ?- qr_code("byakuren", Grid), display_qr(Grid). * * qr_code/2,3,4 backtrack over every encoding that fits the text. * qr_sequence/2,3,4 are the multi-symbol structured-append orchestrators. * They use one symbol when the payload fits, and otherwise split the payload * across a sequence of QR symbols with structured-append headers. qr_sequence/2 * and qr_sequence/3 are the lighter wrappers; qr_sequence/4 also returns the * sequence-level stages and the nested per-symbol stage lists. Each symbol in * the sequence uses the same "best symbol" policy as qr/1,2,3 once its * payload chunk is fixed: smallest fitting version, strongest EC level in that * version, then the lowest-penalty mask. * qr/1,2,3 are the deterministic "best symbol" wrappers: they pick the first * version that fits, prefer stronger error correction within that version, and * then choose the lowest-penalty mask. Simple text input also gets automatic * mixed-mode segmentation there, so the best wrapper can choose segments such * as kanji+alphanumeric instead of forcing the whole payload into one mode. * * Use qr_data([...]) to specify exact QR segment sequences. Use qr_code/3 or * qr_code/4 to inspect the chosen specification and all intermediate stages. * Specs are ordinary property lists: * * [version(Version), level(Level), mode(Mode), mask(Mask)] * * The intended "reasoning interface" is: * - qr/2 and qr/3 when you want rendering plus a spec you can inspect * - qr_sequence/2,3,4 when you want structured-append orchestration * - qr_code/3 and qr_code/4 when you want the pure relation without printing * - qr_decode/2 and qr_decode/3 when you already have textual QR art * - qr_decode_stdin/1 and qr_decode_stdin/2 for shell pipelines * - qr_decode_file/2 and qr_decode_file/3 for saved text-art QR files * - qr_analysis/2 when you want one bundled property-list view of a symbol * - qr_penalty/2 and qr_penalty_breakdown/2 when you want mask-selection analysis * - qr_mask_penalties/3 when you want to compare all masks for one payload/spec * - qr_codewords/4 when you want raw vs corrected codewords directly * - qr_capacity/2 when you want to reason about symbol capacity * - qr_sequence_parity/2 when you want manual structured-append control * - qr_version_size/2, qr_grid_size/2, and qr_grid_version/2 for matrix geometry * - qr_spec/1 when you want to use member/2 safely over a bounded spec shape * - spec_property/2 when you want to constrain a specific spec field directly * * Text decode helpers: * - qr_decode/2,3 accept copied/pasted QR text art directly * - qr_decode_stdin/1,2 read QR text art from standard input * - qr_decode_file/2,3 read QR text art from a file * * Supported textual QR forms: * - compact UTF-8 half blocks: █ ▀ ▄ and spaces * - wide UTF-8 blocks: ██ for black, spaces for white * - single-cell full blocks: █ and spaces * * Recognized ECI text encodings: * - latin1 (ECI 3) * - UTF-16BE (ECI 25) * - UTF-8 (ECI 26) * - ASCII (ECI 27) * * Shell examples: * $ qrencode -t ANSIUTF8 "byakuren" | \ * tpl -g "use_module(qr), qr_decode_stdin(Text, Spec)." * * $ qrencode -t ANSIUTF8 "byakuren" > byakuren-qr.txt * $ tpl -g "use_module(qr), qr_decode_file('byakuren-qr.txt', Text, Spec)." * * Explicit ECI text segments can be written as: * ?- qr_code(qr_data([ascii("ASCII ONLY")]), Grid). * ?- qr_code(qr_data([utf16be("lambda λ")]), Grid). * ?- qr_code(qr_data([eci_text(26, "lambda λ")]), Grid). * * ^ ^ * =(o.o)= * m m * ~byakuren */ :- module(qr, [ qr_code/2, qr_code/3, qr_code/4, qr_sequence/2, qr_sequence/3, qr_sequence/4, qr/1, qr/2, qr/3, qr_decode/2, qr_decode/3, qr_decode_stdin/1, qr_decode_stdin/2, qr_decode_file/2, qr_decode_file/3, qr_analysis/2, qr_penalty/2, qr_penalty_breakdown/2, qr_mask_penalties/3, qr_codewords/4, qr_capacity/2, qr_sequence_parity/2, qr_version_size/2, qr_grid_size/2, qr_grid_version/2, display_qr/1, display_qr_wide/1, qr_render/1, qr_spec/1, spec_property/2, spec_version/2, spec_level/2, spec_mode/2, spec_mask/2, test/0 ]). :- use_module(library(lists)). %% Public API and input recognizers % % qr_code/4 is the main relation. The same public predicate works in both % directions: % % - Text -> Grid : choose a valid spec, encode the payload, lay out a QR % matrix, then return the final binary grid. % - Grid -> Text : read a QR matrix, recover codewords (including erasures % from unknown cells), repair them with Reed-Solomon, then % decode the payload back into text or qr_data(...). % % The Stages list exposes the intermediate artifacts used by the relation. % The most useful stage names are: % % - spec chosen [version(...), level(...), mode(...), mask(...)] % - input, text_codes normalized source text % - stream_items QR segments % - stream_bits payload bits before terminator/padding % - data_codewords payload codewords after padding % - data_blocks Reed-Solomon data blocks % - ecc_blocks Reed-Solomon parity blocks % - codewords final interleaved codewords % - function_grid finder/timing/alignment patterns only % - placed_grid data placed before masking % - masked_grid after applying the selected mask % - grid final rendered QR matrix % - received_* decode-side observations % - extracted_codewords codewords lifted directly from the grid % - rs_corrections repairs inferred by Reed-Solomon decoding %% qr_code(?Data, ?Grid) is nondet. %% qr_code(?Data, ?Grid, ?Spec) is nondet. %% qr_code(?Data, ?Grid, ?Spec, ?Stages) is nondet. % % Main relational interface for one QR symbol. % % `Data` is plain text or `qr_data([...])`. `Grid` is a square 2D list of QR % modules. `Spec` is `[version(...), level(...), mode(...), mask(...)]`. qr_code(Text, Grid) :- qr_code(Text, Grid, _Spec, _Stages). qr_code(Text, Grid, Spec) :- qr_code(Text, Grid, Spec, _Stages). % Encode path: payload -> codewords -> grid. qr_code(Text, Grid, Spec, Stages) :- qr_input_data(Text), qr_spec_shape(Spec, _Version, _Level, _Mode, _Mask), qr_stream_codewords(Spec, Text, Codewords, StreamStages), qr_grid_codewords(Spec, Codewords, Grid, MatrixStages), append([stage(spec, Spec)|StreamStages], MatrixStages, Stages). % Decode path: grid -> received codewords -> repaired payload. qr_code(Text, Grid, Spec, Stages) :- \+ qr_input_data(Text), qr_input_grid(Grid), qr_spec_shape(Spec, _Version, _Level, _Mode, _Mask), qr_grid_codewords(Spec, ReceivedCodewords, Grid, ExtractStages), qr_stream_codewords(Spec, Text, ReceivedCodewords, StreamStages), member(stage(codewords, Codewords), StreamStages), qr_grid_codewords(Spec, Codewords, CorrectedGrid, MatrixStages), fill_unknown_grid_cells(Grid, CorrectedGrid), append([stage(spec, Spec)|ExtractStages], StreamStages, Stages0), append(Stages0, MatrixStages, Stages). % Recognize the payload side of qr_code/*. qr_input_data(qr_data(Items)) :- nonvar(Items), proper_list(Items). qr_input_data(Text) :- atom(Text). qr_input_data(Text) :- Text == []. qr_input_data([Item|Items]) :- qr_text_item(Item), qr_text_items(Items). % Recognize the grid side of qr_code/*. Unknown cells may be `u` or variables. qr_input_grid(Grid) :- nonvar(Grid), Grid = [Row|Rows], qr_input_row(Row), length(Row, Size), qr_input_grid_rows(Rows, Size). qr_text_items([]). qr_text_items([Item|Items]) :- qr_text_item(Item), qr_text_items(Items). qr_text_item(Item) :- integer(Item). qr_text_item(Item) :- atom(Item), atom_length(Item, 1). qr_input_grid_rows([], _Size). qr_input_grid_rows([Row|Rows], Size) :- qr_input_row(Row), length(Row, Size), qr_input_grid_rows(Rows, Size). qr_input_row(Row) :- nonvar(Row), Row = [Bit|Bits], qr_input_bit(Bit), qr_input_row_bits(Bits). qr_input_row_bits([]). qr_input_row_bits([Bit|Bits]) :- qr_input_bit(Bit), qr_input_row_bits(Bits). binary_bit(Bit) :- integer(Bit), (Bit =:= 0 ; Bit =:= 1). qr_input_bit(Bit) :- binary_bit(Bit). qr_input_bit(Bit) :- var(Bit). qr_input_bit(u). qr_codeword_sequence([Word|Words]) :- qr_codeword(Word), qr_codeword_sequence_rest(Words). qr_codeword_sequence_rest([]). qr_codeword_sequence_rest([Word|Words]) :- qr_codeword(Word), qr_codeword_sequence_rest(Words). qr_codeword(Word) :- integer(Word), Word >= 0, Word =< 255. qr_received_codeword_sequence([Word|Words]) :- qr_received_codeword(Word), qr_received_codeword_sequence_rest(Words). qr_received_codeword_sequence_rest([]). qr_received_codeword_sequence_rest([Word|Words]) :- qr_received_codeword(Word), qr_received_codeword_sequence_rest(Words). qr_received_codeword(Word) :- qr_codeword(Word). qr_received_codeword(erasure). %% qr(+Data) is semidet. %% qr(+Data, ?Spec) is semidet. %% qr(+Data, ?Spec, -Grid) is semidet. % % Deterministic convenience wrappers around qr_code/*. % % They render one best-choice symbol instead of backtracking over all valid % encodings. qr(Text) :- qr_solution(Text, Spec, Grid), write('Spec: '), write(Spec), nl, qr_show(Grid), !. qr(Text, Spec) :- qr_solution(Text, Spec, Grid), qr_show(Grid), !. qr(Text, Spec, Grid) :- qr_solution(Text, Spec, Grid), qr_show(Grid), !. % qr_solution/3 is the deterministic "best symbol" relation used by qr/1..3. % It chooses the smallest fitting version, the strongest EC level in that % version, and the lowest-penalty mask. qr_solution(Text, Spec, Grid) :- qr_input_data(Text), qr_spec_shape(Spec, Version, Level, Mode, Mask), select_version(Version), findall(Candidate, qr_solution_candidate(Text, Version, Level, Mode, Mask, Candidate), Candidates), Candidates = [_|_], best_qr_candidate(Candidates, candidate(_Key, BestSpec, Grid)), Spec = BestSpec, !. qr_show(Grid) :- display_qr(Grid), nl, !. %% qr_sequence(?Data, ?Grids) is semidet. %% qr_sequence(?Data, ?Grids, ?Specs) is semidet. %% qr_sequence(?Data, ?Grids, ?Specs, ?Stages) is semidet. % % Structured-append orchestration for multi-symbol payloads. % % Uses one symbol when possible, otherwise splits the payload across a valid % structured-append sequence. qr_sequence(Data, Grids) :- qr_sequence(Data, Grids, _Specs). qr_sequence(Data, Grids, Specs) :- qr_sequence_relation(no_stages, Data, Grids, Specs, _Stages). qr_sequence(Data, Grids, Specs, Stages) :- qr_sequence_relation(with_stages, Data, Grids, Specs, Stages). qr_sequence_relation(StageMode, Data, Grids, Specs, Stages) :- qr_input_data(Data), !, qr_sequence_encode(StageMode, Data, Grids, Specs, Stages). qr_sequence_relation(StageMode, Data, Grids, Specs, Stages) :- \+ qr_input_data(Data), qr_input_grid_sequence(Grids), qr_sequence_decode(StageMode, Data, Grids, Specs, Stages). qr_input_grid_sequence(Grids) :- nonvar(Grids), Grids = [Grid|RestGrids], qr_input_grid(Grid), qr_input_grid_sequence_rest(RestGrids). qr_input_grid_sequence_rest([]). qr_input_grid_sequence_rest([Grid|Grids]) :- qr_input_grid(Grid), qr_input_grid_sequence_rest(Grids). % Sequence encoding first prefers a single symbol when that is still plausible. % The quick fit check below works at the payload/codeword layer: it asks whether % the payload can be turned into a valid Version 40 / level L data stream at % all. If not, the orchestrator skips the dead single-symbol branch and goes % straight to structured append. single_symbol_candidate(Data) :- qr_input_data(Data), single_symbol_payload_fits(Data). single_symbol_payload_fits(Data) :- qr_solution_items(Data, 40, _Mode, Items, _Summary), qr_solution_codewords(40, l, Items, _StreamBits, _Codewords). qr_sequence_encode(no_stages, Data, [Grid], [Spec], []) :- single_symbol_candidate(Data), qr_solution(Data, Spec, Grid), !. qr_sequence_encode(no_stages, Data, Grids, Specs, []) :- qr_sequence_parity(Data, Parity), qr_between(2, 16, Count), TotalField is Count - 1, qr_sequence_symbols_quick(Data, Count, TotalField, Parity, Symbols), sequence_symbol_grids(Symbols, Grids), sequence_symbol_specs(Symbols, Specs), !. qr_sequence_encode(with_stages, Data, Grids, Specs, Stages) :- qr_sequence_encode_staged(Data, Grids, Specs, Stages). qr_sequence_encode_staged(Data, [Grid], [Spec], Stages) :- single_symbol_candidate(Data), qr_solution(Data, Spec, Grid), qr_code(Data, Grid, Spec, SymbolStages), Stages = [ stage(sequence_total, 1), stage(sequence_symbols, [symbol(0, Data, Spec, Grid, SymbolStages)]) ], !. qr_sequence_encode_staged(Data, Grids, Specs, Stages) :- qr_sequence_parity(Data, Parity), qr_between(2, 16, Count), TotalField is Count - 1, qr_sequence_symbols(Data, Count, TotalField, Parity, Symbols), sequence_symbol_grids(Symbols, Grids), sequence_symbol_specs(Symbols, Specs), sequence_stage_symbols(Symbols, StageSymbols), sequence_payload_items(Symbols, PayloadItems), Stages = [ stage(sequence_total, Count), stage(sequence_parity, Parity), stage(sequence_symbols, StageSymbols), stage(sequence_items, PayloadItems) ], !. qr_sequence_symbols_quick(qr_data(RawItems), Count, TotalField, Parity, Symbols) :- normalize_qr_items(RawItems, Items), structured_append_free_items(Items), qr_sequence_item_symbols_quick(Items, 0, Count, TotalField, Parity, Symbols). qr_sequence_symbols_quick(Data, Count, TotalField, Parity, Symbols) :- text_codes(Data, Codes), qr_sequence_text_symbols_quick(Codes, Count, TotalField, Parity, Symbols). qr_sequence_text_symbols_quick(Codes, Count, TotalField, Parity, Symbols) :- balanced_text_chunks(Codes, Count, ChunkCodesList), qr_sequence_text_symbols_quick(ChunkCodesList, 0, TotalField, Parity, Symbols). qr_sequence_text_symbols_quick([], _Index, _TotalField, _Parity, []). qr_sequence_text_symbols_quick([ChunkCodes|ChunkCodesList], Index, TotalField, Parity, [Symbol|Symbols]) :- codes_text(ChunkCodes, ChunkText), qr_sequence_text_symbol_quick(ChunkText, Index, TotalField, Parity, Symbol), Index1 is Index + 1, qr_sequence_text_symbols_quick(ChunkCodesList, Index1, TotalField, Parity, Symbols). qr_sequence_item_symbols_quick([], Count, Count, _TotalField, _Parity, []). qr_sequence_item_symbols_quick(Items, Index, Count, TotalField, Parity, [Symbol|Symbols]) :- Index < Count, RemainingSymbols is Count - Index - 1, list_prefix_desc(Items, RemainingSymbols, PayloadItems, RestItems), qr_sequence_item_symbol_quick(PayloadItems, Index, TotalField, Parity, Symbol), Index1 is Index + 1, qr_sequence_item_symbols_quick(RestItems, Index1, Count, TotalField, Parity, Symbols). qr_sequence_text_symbol_quick(ChunkText, Index, TotalField, Parity, seq_symbol(Index, TotalField, Parity, PayloadItems, SymbolData, Spec, Grid, [])) :- qr_sequence_text_symbol_core(ChunkText, Index, TotalField, Parity, PayloadItems, SymbolData, Spec, Grid), !. qr_sequence_item_symbol_quick(PayloadItems, Index, TotalField, Parity, seq_symbol(Index, TotalField, Parity, PayloadItems, SymbolData, Spec, Grid, [])) :- qr_sequence_item_symbol_core(PayloadItems, Index, TotalField, Parity, SymbolData, Spec, Grid). qr_sequence_symbols(qr_data(RawItems), Count, TotalField, Parity, Symbols) :- normalize_qr_items(RawItems, Items), structured_append_free_items(Items), qr_sequence_item_symbols(Items, 0, Count, TotalField, Parity, Symbols). qr_sequence_symbols(Data, Count, TotalField, Parity, Symbols) :- text_codes(Data, Codes), qr_sequence_text_symbols(Codes, Count, TotalField, Parity, Symbols). qr_sequence_text_symbols(Codes, Count, TotalField, Parity, Symbols) :- balanced_text_chunks(Codes, Count, ChunkCodesList), qr_sequence_text_symbols(ChunkCodesList, 0, TotalField, Parity, Symbols). qr_sequence_text_symbols([], _Index, _TotalField, _Parity, []). qr_sequence_text_symbols([ChunkCodes|ChunkCodesList], Index, TotalField, Parity, [Symbol|Symbols]) :- codes_text(ChunkCodes, ChunkText), qr_sequence_text_symbol(ChunkText, Index, TotalField, Parity, Symbol), Index1 is Index + 1, qr_sequence_text_symbols(ChunkCodesList, Index1, TotalField, Parity, Symbols). qr_sequence_item_symbols([], Count, Count, _TotalField, _Parity, []). qr_sequence_item_symbols(Items, Index, Count, TotalField, Parity, [Symbol|Symbols]) :- Index < Count, RemainingSymbols is Count - Index - 1, list_prefix_desc(Items, RemainingSymbols, PayloadItems, RestItems), qr_sequence_item_symbol(PayloadItems, Index, TotalField, Parity, Symbol), Index1 is Index + 1, qr_sequence_item_symbols(RestItems, Index1, Count, TotalField, Parity, Symbols). qr_sequence_text_symbol(ChunkText, Index, TotalField, Parity, seq_symbol(Index, TotalField, Parity, PayloadItems, SymbolData, Spec, Grid, SymbolStages)) :- qr_sequence_text_symbol_core(ChunkText, Index, TotalField, Parity, PayloadItems, SymbolData, Spec, Grid), qr_code(SymbolData, Grid, Spec, SymbolStages). qr_sequence_item_symbol(PayloadItems, Index, TotalField, Parity, seq_symbol(Index, TotalField, Parity, PayloadItems, SymbolData, Spec, Grid, SymbolStages)) :- qr_sequence_item_symbol_core(PayloadItems, Index, TotalField, Parity, SymbolData, Spec, Grid), qr_code(SymbolData, Grid, Spec, SymbolStages). % The staged and no-stage sequence wrappers share the same symbol-selection % logic; they differ only in whether qr_code/4 is called afterward to expose % detailed symbol stages. qr_sequence_text_symbol_core(ChunkText, Index, TotalField, Parity, PayloadItems, SymbolData, Spec, Grid) :- version_group_range(Group, LowVersion, HighVersion), best_text_items_for_group(Group, ChunkText, PayloadItems), sequence_symbol_data(Index, TotalField, Parity, PayloadItems, SymbolData), sequence_symbol_items(Index, TotalField, Parity, PayloadItems, SymbolItems), best_symbol_for_items(SymbolItems, LowVersion, HighVersion, Spec, Grid), !. qr_sequence_item_symbol_core(PayloadItems, Index, TotalField, Parity, SymbolData, Spec, Grid) :- sequence_symbol_data(Index, TotalField, Parity, PayloadItems, SymbolData), sequence_symbol_items(Index, TotalField, Parity, PayloadItems, SymbolItems), best_symbol_for_items(SymbolItems, 1, 40, Spec, Grid). version_group_range(small, 1, 9). version_group_range(medium, 10, 26). version_group_range(large, 27, 40). best_text_items_for_group(small, Text, Items) :- best_sequence_text_items(1, Text, Items). best_text_items_for_group(medium, Text, Items) :- best_sequence_text_items(10, Text, Items). best_text_items_for_group(large, Text, Items) :- best_sequence_text_items(27, Text, Items). % Large structured-append chunks can be thousands of characters long. For % those chunks, a whole-text mode choice is usually enough and is much cheaper % than the full mixed-segmentation dynamic program. Smaller chunks still use % the exact best_text_items_for_version/3 search. best_sequence_text_items(Version, Text, Items) :- text_codes(Text, Codes), length(Codes, CodeCount), ( CodeCount > 128 -> best_whole_text_items_for_version(Version, Codes, Items) ; best_text_items_for_version(Version, Text, Items) ). best_whole_text_items_for_version(Version, Codes, Items) :- findall(candidate(Key, CandidateItems), whole_text_items_candidate(Version, Codes, candidate(Key, CandidateItems)), Candidates), Candidates = [Candidate|RestCandidates], best_whole_text_candidate(RestCandidates, Candidate, candidate(_Key, Items)). whole_text_items_candidate(Version, Codes, candidate(Key, Items)) :- text_mode_items(Codes, Mode, Items), items_bits(Version, Items, stream_state(none, default), _FinalState, _ItemStages, Bits), length(Bits, BitCount), length(Items, SegmentCount), mode_rank(Mode, ModeRank), Key = key(BitCount, SegmentCount, ModeRank). best_whole_text_candidate([], BestCandidate, BestCandidate). best_whole_text_candidate([Candidate|Candidates], Candidate0, BestCandidate) :- better_whole_text_candidate(Candidate, Candidate0), !, best_whole_text_candidate(Candidates, Candidate, BestCandidate). best_whole_text_candidate([_Candidate|Candidates], Candidate0, BestCandidate) :- best_whole_text_candidate(Candidates, Candidate0, BestCandidate). better_whole_text_candidate(candidate(Key, _Items), candidate(Key0, _Items0)) :- Key @< Key0. % sequence_symbol_items/5 adds the structured-append control header to one % symbol's payload items. The resulting internal item list is what actually % gets encoded onto that QR symbol. sequence_symbol_items(Index, TotalField, Parity, PayloadItems, [structured_append(Index, TotalField, Parity)|PayloadItems]). sequence_symbol_data(Index, TotalField, Parity, PayloadItems, qr_data(SymbolItems)) :- sequence_symbol_items(Index, TotalField, Parity, PayloadItems, InternalSymbolItems), denormalize_qr_items(InternalSymbolItems, SymbolItems). % best_symbol_for_items/5 is the structured-append analogue of qr_solution/3 % for a fixed segment list. Once one symbol's payload items are known it uses % exactly the same policy as qr/1..3: % % - choose the smallest version in the allowed range that fits % - choose the strongest EC level in that version % - choose the lowest-penalty mask under the QR mask-selection score best_symbol_for_items(Items, LowVersion, HighVersion, Spec, Grid) :- items_summary_mode(Items, Mode), qr_between(LowVersion, HighVersion, Version), findall(candidate(Key, CandidateSpec, CandidateGrid), symbol_candidate_for_items(Items, Version, Mode, candidate(Key, CandidateSpec, CandidateGrid)), Candidates), Candidates = [_|_], best_qr_candidate(Candidates, candidate(_Key, Spec, Grid)), !. symbol_candidate_for_items(Items, Version, Mode, candidate(Key, Spec, Grid)) :- select_level(Level), qr_solution_codewords(Version, Level, Items, StreamBits, Codewords), select_mask(Mask), Spec = [ version(Version), level(Level), mode(Mode), mask(Mask) ], qr_grid_codewords(Spec, Codewords, Grid, _GridStages), qr_candidate_key(Spec, Grid, StreamBits, Items, Key). structured_append_free_items([]). structured_append_free_items([structured_append(_Index, _TotalField, _Parity)|_Items]) :- !, fail. structured_append_free_items([_Item|Items]) :- structured_append_free_items(Items). qr_sequence_decode_staged(Data, Grids, Specs, Stages) :- qr_sequence_structured_decode(Data, Grids, Specs, Stages), !. qr_sequence_decode_staged(Data, [Grid], [Spec], Stages) :- qr_code(Data, Grid, Spec, SymbolStages), Stages = [ stage(sequence_total, 1), stage(sequence_symbols, [symbol(0, Data, Spec, Grid, SymbolStages)]) ]. qr_sequence_structured_decode(Data, Grids, Specs, Stages) :- decode_sequence_symbols(Grids, Symbols0), validate_sequence_symbols(Symbols0, Count, Parity, Symbols), sequence_symbol_specs(Symbols, Specs), sequence_stage_symbols(Symbols, StageSymbols), sequence_payload_items(Symbols, PayloadItems), decode_stream_data(PayloadItems, Data), Stages = [ stage(sequence_total, Count), stage(sequence_parity, Parity), stage(sequence_symbols, StageSymbols), stage(sequence_items, PayloadItems) ]. qr_sequence_decode(no_stages, Data, Grids, Specs, []) :- qr_sequence_structured_decode_quick(Data, Grids, Specs), !. qr_sequence_decode(no_stages, Data, [Grid], [Spec], []) :- qr_code(Data, Grid, Spec). qr_sequence_decode(with_stages, Data, Grids, Specs, Stages) :- qr_sequence_decode_staged(Data, Grids, Specs, Stages). decode_sequence_symbols([], []). decode_sequence_symbols([Grid|Grids], [Symbol|Symbols]) :- decode_sequence_symbol(Grid, Symbol), decode_sequence_symbols(Grids, Symbols). decode_sequence_symbol(Grid, seq_symbol(Index, TotalField, Parity, PayloadItems, SymbolData, Spec, Grid, SymbolStages)) :- qr_code(SymbolData, Grid, Spec, SymbolStages), structured_append_symbol_data(SymbolData, Index, TotalField, Parity, PayloadItems). structured_append_symbol_data(qr_data(SymbolItems0), Index, TotalField, Parity, PayloadItems) :- normalize_qr_items(SymbolItems0, SymbolItems), SymbolItems = [structured_append(Index, TotalField, Parity)|PayloadItems]. qr_sequence_structured_decode_quick(Data, Grids, Specs) :- decode_sequence_symbols_quick(Grids, Symbols0), validate_sequence_symbols(Symbols0, _Count, _Parity, Symbols), sequence_symbol_specs(Symbols, Specs), sequence_payload_items(Symbols, PayloadItems), decode_stream_data(PayloadItems, Data). decode_sequence_symbols_quick([], []). decode_sequence_symbols_quick([Grid|Grids], [Symbol|Symbols]) :- decode_sequence_symbol_quick(Grid, Symbol), decode_sequence_symbols_quick(Grids, Symbols). decode_sequence_symbol_quick(Grid, seq_symbol(Index, TotalField, Parity, PayloadItems, SymbolData, Spec, Grid, [])) :- qr_code(SymbolData, Grid, Spec), structured_append_symbol_data(SymbolData, Index, TotalField, Parity, PayloadItems). validate_sequence_symbols(Symbols0, Count, Parity, Symbols) :- Symbols0 = [seq_symbol(_Index, TotalField, Parity, _PayloadItems, _SymbolData, _Spec, _Grid, _Stages)|_], same_total_field_symbols(Symbols0, TotalField), same_parity_symbols(Symbols0, Parity), Count is TotalField + 1, length(Symbols0, Count), sort_sequence_symbols(Symbols0, Symbols), sequence_indices(Symbols, Indices), expected_sequence_indices(0, TotalField, Indices). same_total_field_symbols([], _TotalField). same_total_field_symbols([seq_symbol(_Index, TotalField, _Parity, _PayloadItems, _SymbolData, _Spec, _Grid, _Stages)|Symbols], TotalField) :- same_total_field_symbols(Symbols, TotalField). same_parity_symbols([], _Parity). same_parity_symbols([seq_symbol(_Index, _TotalField, Parity, _PayloadItems, _SymbolData, _Spec, _Grid, _Stages)|Symbols], Parity) :- same_parity_symbols(Symbols, Parity). sort_sequence_symbols([], []). sort_sequence_symbols([Symbol|Symbols], SortedSymbols) :- sort_sequence_symbols(Symbols, SortedSymbols0), insert_sequence_symbol(Symbol, SortedSymbols0, SortedSymbols). insert_sequence_symbol(Symbol, [], [Symbol]). insert_sequence_symbol(seq_symbol(Index, TotalField, Parity, PayloadItems, SymbolData, Spec, Grid, Stages), [seq_symbol(Index0, TotalField0, Parity0, PayloadItems0, SymbolData0, Spec0, Grid0, Stages0)|Symbols], [seq_symbol(Index, TotalField, Parity, PayloadItems, SymbolData, Spec, Grid, Stages), seq_symbol(Index0, TotalField0, Parity0, PayloadItems0, SymbolData0, Spec0, Grid0, Stages0) |Symbols]) :- Index =< Index0, !. insert_sequence_symbol(Symbol, [Head|Symbols], [Head|SortedSymbols]) :- insert_sequence_symbol(Symbol, Symbols, SortedSymbols). sequence_indices([], []). sequence_indices([seq_symbol(Index, _TotalField, _Parity, _PayloadItems, _SymbolData, _Spec, _Grid, _Stages)|Symbols], [Index|Indices]) :- sequence_indices(Symbols, Indices). expected_sequence_indices(Next, TotalField, []) :- Next > TotalField, !. expected_sequence_indices(Next, TotalField, [Next|Indices]) :- Next =< TotalField, Next1 is Next + 1, expected_sequence_indices(Next1, TotalField, Indices). sequence_symbol_grids([], []). sequence_symbol_grids([seq_symbol(_Index, _TotalField, _Parity, _PayloadItems, _SymbolData, _Spec, Grid, _Stages)|Symbols], [Grid|Grids]) :- sequence_symbol_grids(Symbols, Grids). sequence_symbol_specs([], []). sequence_symbol_specs([seq_symbol(_Index, _TotalField, _Parity, _PayloadItems, _SymbolData, Spec, _Grid, _Stages)|Symbols], [Spec|Specs]) :- sequence_symbol_specs(Symbols, Specs). sequence_stage_symbols([], []). sequence_stage_symbols([seq_symbol(Index, _TotalField, _Parity, _PayloadItems, SymbolData, Spec, Grid, Stages)|Symbols], [symbol(Index, SymbolData, Spec, Grid, Stages)|StageSymbols]) :- sequence_stage_symbols(Symbols, StageSymbols). sequence_payload_items([], []). sequence_payload_items([seq_symbol(_Index, _TotalField, _Parity, PayloadItems, _SymbolData, _Spec, _Grid, _Stages)|Symbols], Items) :- sequence_payload_items(Symbols, RestItems), append(PayloadItems, RestItems, Items). %% qr_sequence_parity(+Data, -Parity) is semidet. % % Compute the structured-append parity byte for a payload or explicit % `qr_data([...])` stream. % % This is mainly useful when you want to inspect or construct % `structured_append/3` segments manually rather than using qr_sequence/*. qr_sequence_parity(qr_data(RawItems), Parity) :- normalize_qr_items(RawItems, Items), structured_append_free_items(Items), sequence_items_bytes(Items, Bytes), xor_bytes(Bytes, 0, Parity). qr_sequence_parity(Data, Parity) :- text_codes(Data, Codes), text_parity_bytes(Codes, Bytes), xor_bytes(Bytes, 0, Parity). sequence_items_bytes([], []). sequence_items_bytes([numeric(Codes)|Items], Bytes) :- text_parity_bytes(Codes, ItemBytes), sequence_items_bytes(Items, RestBytes), append(ItemBytes, RestBytes, Bytes). sequence_items_bytes([alphanumeric(Codes)|Items], Bytes) :- text_parity_bytes(Codes, ItemBytes), sequence_items_bytes(Items, RestBytes), append(ItemBytes, RestBytes, Bytes). sequence_items_bytes([byte(ItemBytes)|Items], Bytes) :- sequence_items_bytes(Items, RestBytes), append(ItemBytes, RestBytes, Bytes). sequence_items_bytes([kanji(Codes)|Items], Bytes) :- text_parity_bytes(Codes, ItemBytes), sequence_items_bytes(Items, RestBytes), append(ItemBytes, RestBytes, Bytes). sequence_items_bytes([eci(_Assignment)|Items], Bytes) :- sequence_items_bytes(Items, Bytes). sequence_items_bytes([fnc1(first)|Items], Bytes) :- sequence_items_bytes(Items, Bytes). sequence_items_bytes([fnc1(second, Indicator)|Items], [Indicator|Bytes]) :- sequence_items_bytes(Items, Bytes). text_parity_bytes(Codes, Bytes) :- ( valid_bytes(Codes) -> Bytes = Codes ; utf8_bytes_from_codes(Codes, Bytes) ). balanced_text_chunks(Codes, Count, ChunkCodesList) :- integer(Count), Count > 0, length(Codes, Length), Count =< Length, balanced_chunk_lengths(Length, Count, ChunkLengths), split_by_lengths(Codes, ChunkLengths, ChunkCodesList). balanced_chunk_lengths(Length, Count, Lengths) :- integer(Count), Count > 0, BaseLength is Length div Count, ExtraCount is Length mod Count, balanced_chunk_lengths(Count, BaseLength, ExtraCount, Lengths). balanced_chunk_lengths(0, _BaseLength, _ExtraCount, []). balanced_chunk_lengths(Count, BaseLength, ExtraCount, [Length|Lengths]) :- Count > 0, ( ExtraCount > 0 -> Length is BaseLength + 1, ExtraCount1 is ExtraCount - 1 ; Length = BaseLength, ExtraCount1 = ExtraCount ), Count1 is Count - 1, balanced_chunk_lengths(Count1, BaseLength, ExtraCount1, Lengths). split_by_lengths([], [], []). split_by_lengths(Codes, [Length|Lengths], [ChunkCodes|ChunkCodesList]) :- split_at(Length, Codes, ChunkCodes, RestCodes), split_by_lengths(RestCodes, Lengths, ChunkCodesList). xor_bytes([], Parity, Parity). xor_bytes([Byte|Bytes], Parity0, Parity) :- byte_xor(Parity0, Byte, Parity1), xor_bytes(Bytes, Parity1, Parity). byte_xor(A, B, Xor) :- Xor is (A \/ B) /\ \(A /\ B). list_prefix_desc(List, MinSuffixLength, Prefix, Suffix) :- length(List, Length), MaxPrefixLength is Length - MinSuffixLength, MaxPrefixLength >= 1, qr_between_desc(MaxPrefixLength, 1, PrefixLength), split_at(PrefixLength, List, Prefix, Suffix). qr_between_desc(High, Low, High) :- High >= Low. qr_between_desc(High, Low, Value) :- High > Low, High1 is High - 1, qr_between_desc(High1, Low, Value). % qr_solution_candidate/6 enumerates candidates for one fixed version. The % candidate key encodes the library's "best symbol" policy: % - stronger EC level first % - then lower penalty % - then shorter payload bitstream % - then fewer segments % - then lower mask number % - then a stable mode preference %% qr_solution_candidate(+Data, %% +Version, %% ?Level, %% ?Mode, %% ?Mask, %% -Candidate) is nondet. % % Enumerate one candidate symbol for the deterministic qr/* wrappers. qr_solution_candidate(Text, Version, LevelConstraint, ModeConstraint, MaskConstraint, candidate(Key, Spec, Grid)) :- qr_solution_items(Text, Version, ModeConstraint, Items, Mode), LevelConstraint = Level, select_level(Level), qr_solution_codewords(Version, Level, Items, StreamBits, Codewords), MaskConstraint = Mask, select_mask(Mask), Spec = [version(Version), level(Level), mode(Mode), mask(Mask)], qr_grid_codewords(Spec, Codewords, Grid, _GridStages), qr_candidate_key(Spec, Grid, StreamBits, Items, Key). qr_solution_items(qr_data(RawItems), _Version, ModeConstraint, Items, Mode) :- normalize_qr_items(RawItems, Items), items_summary_mode(Items, Mode), ModeConstraint = Mode. qr_solution_items(Text, Version, ModeConstraint, Items, Mode) :- text_codes(Text, Codes), qr_solution_text_items(Codes, Version, Text, ModeConstraint, Items, Mode). qr_solution_text_items([], _Version, _Text, ModeConstraint, Items, Mode) :- empty_text_solution_items(ModeConstraint, Items, Mode). qr_solution_text_items(Codes, Version, Text, ModeConstraint, Items, Mode) :- Codes \= [], ( var(ModeConstraint) -> best_text_items_for_version(Version, Text, Items), items_summary_mode(Items, Mode) ; ModeConstraint == segments -> best_text_items_for_version(Version, Text, Items), items_summary_mode(Items, Mode), Mode == segments ; select_text_items(Codes, ModeConstraint, Items, Mode) ). empty_text_solution_items(ModeConstraint, [byte([])], byte) :- ( var(ModeConstraint) ; ModeConstraint == byte ), !. empty_text_solution_items(utf8, [eci(26), byte([])], utf8). qr_solution_codewords(Version, Level, Items, StreamBits, Codewords) :- encode_data_words(Version, Level, Items, _ItemStages, StreamBits, _DataBits, DataWords), rs_blocks(Version, Level, Blocks), blocks_data_words(DataWords, Blocks, DataBlocks), blocks_ecc_words(DataBlocks, Blocks, EccBlocks), interleave_codewords(DataBlocks, EccBlocks, Codewords). qr_candidate_key(Spec, Grid, StreamBits, Items, key(LevelRank, Penalty, StreamBitCount, SegmentCount, Mask, ModeRank)) :- spec_level(Spec, Level), spec_mask(Spec, Mask), spec_mode(Spec, Mode), level_rank(Level, LevelRank), mode_rank(Mode, ModeRank), qr_penalty(Grid, Penalty), length(StreamBits, StreamBitCount), length(Items, SegmentCount). best_qr_candidate([Candidate|Candidates], BestCandidate) :- best_qr_candidate(Candidates, Candidate, BestCandidate). best_qr_candidate([], BestCandidate, BestCandidate). best_qr_candidate([Candidate|Candidates], Candidate0, BestCandidate) :- qr_candidate_better(Candidate, Candidate0), !, best_qr_candidate(Candidates, Candidate, BestCandidate). best_qr_candidate([_Candidate|Candidates], Candidate0, BestCandidate) :- best_qr_candidate(Candidates, Candidate0, BestCandidate). qr_candidate_better(candidate(Key, _Spec, _Grid), candidate(Key0, _Spec0, _Grid0)) :- Key @< Key0. level_rank(h, 0). level_rank(q, 1). level_rank(m, 2). level_rank(l, 3). mode_rank(numeric, 0). mode_rank(alphanumeric, 1). mode_rank(kanji, 2). mode_rank(byte, 3). mode_rank(utf8, 4). mode_rank(segments, 5). % qr_decode/2 and qr_decode/3 read textual QR art, recover the binary matrix, % then reuse qr_code/4 for the actual payload decode. % %% qr_decode(+Textual, -Data) is semidet. %% qr_decode(+Textual, -Data, -Spec) is semidet. %% qr_decode_stdin(-Data) is semidet. %% qr_decode_stdin(-Data, -Spec) is semidet. %% qr_decode_file(+Path, -Data) is semidet. %% qr_decode_file(+Path, -Data, -Spec) is semidet. % % Decode copied, piped, or file-backed textual QR art. % % Supports compact half-block art, wide `██` output, and single-cell `█` % output, with permissive handling of borders, ANSI colour, and inversion. qr_decode(Textual, Data) :- qr_decode(Textual, Data, _Spec). qr_decode(Textual, Data, Spec) :- qr_decode_text(Textual, Data, Spec), !. qr_decode_stdin(Data) :- qr_decode_stdin(Data, _Spec). qr_decode_stdin(Data, Spec) :- current_input(Stream), qr_decode_stream(Stream, Data, Spec), !. qr_decode_file(Path, Data) :- qr_decode_file(Path, Data, _Spec). qr_decode_file(Path, Data, Spec) :- open(Path, read, Stream), read_stream_codes(Stream, Textual), close(Stream), qr_decode(Textual, Data, Spec), !. qr_decode_stream(Stream, Data, Spec) :- read_stream_codes(Stream, Textual), qr_decode(Textual, Data, Spec), !. qr_decode_text(Textual, Data, Spec) :- qr_text_grid(Textual, Grid), qr_code(Data, Grid, Spec, _Stages). qr_text_grid(Textual, Grid) :- qr_text_lines(Textual, Lines), qr_text_lines_grid(Lines, RawGrid0), qr_text_polarity_grid(RawGrid0, RawGrid), normalize_qr_text_grid(RawGrid, Grid). read_stream_codes(Stream, Codes) :- get_code(Stream, Code), read_stream_codes_rest(Code, Stream, Codes). read_stream_codes_rest(Code, _Stream, []) :- stream_end_code(Code), !. read_stream_codes_rest(Code, Stream, [Code|Codes]) :- get_code(Stream, NextCode), read_stream_codes_rest(NextCode, Stream, Codes). stream_end_code(-1). stream_end_code(end_of_file). qr_text_lines(Textual, Lines) :- qr_text_line_list(Textual, LineTexts), normalize_qr_text_lines(LineTexts, Lines). qr_text_lines(Textual, Lines) :- \+ qr_text_line_list(Textual, _LineTexts), text_codes(Textual, Codes), strip_ansi_codes(Codes, CleanCodes), split_text_lines(CleanCodes, RawLines0), trim_blank_text_lines(RawLines0, RawLines), pad_text_lines(RawLines, Lines). qr_text_line_list(LineTexts0, LineTexts) :- nonvar(LineTexts0), LineTexts0 = [LineText|LineTexts0Tail], qr_text_line_item(LineText), qr_text_line_items(LineTexts0Tail), LineTexts = [LineText|LineTexts0Tail]. qr_text_line_items([]). qr_text_line_items([LineText|LineTexts]) :- qr_text_line_item(LineText), qr_text_line_items(LineTexts). qr_text_line_item(LineText) :- nonvar(LineText), proper_list(LineText). qr_text_line_item(LineText) :- nonvar(LineText), atom(LineText), atom_length(LineText, Length), Length =\= 1. normalize_qr_text_lines(LineTexts, Lines) :- maplist(line_text_codes, LineTexts, RawLines0), maplist(strip_ansi_codes, RawLines0, RawLines1), trim_blank_text_lines(RawLines1, RawLines), pad_text_lines(RawLines, Lines). line_text_codes(LineText, Codes) :- text_codes(LineText, Codes). strip_ansi_codes([], []). strip_ansi_codes([27,91|Codes], CleanCodes) :- !, strip_csi_sequence(Codes, RestCodes), strip_ansi_codes(RestCodes, CleanCodes). strip_ansi_codes([Code|Codes], [Code|CleanCodes]) :- strip_ansi_codes(Codes, CleanCodes). strip_csi_sequence([], []). strip_csi_sequence([Code|Codes], Codes) :- ansi_final_code(Code), !. strip_csi_sequence([_Code|Codes], RestCodes) :- strip_csi_sequence(Codes, RestCodes). ansi_final_code(Code) :- integer(Code), Code >= 64, Code =< 126. split_text_lines(Codes, Lines) :- split_text_lines(Codes, [], [], RevLines), reverse(RevLines, Lines). split_text_lines([], CurrentRev, LinesRev, [Line|LinesRev]) :- reverse(CurrentRev, Line). split_text_lines([10|Codes], CurrentRev, LinesRev, Lines) :- reverse(CurrentRev, Line), split_text_lines(Codes, [], [Line|LinesRev], Lines). split_text_lines([13|Codes], CurrentRev, LinesRev, Lines) :- split_text_lines(Codes, CurrentRev, LinesRev, Lines). split_text_lines([Code|Codes], CurrentRev, LinesRev, Lines) :- Code =\= 10, Code =\= 13, split_text_lines(Codes, [Code|CurrentRev], LinesRev, Lines). trim_blank_text_lines(Lines0, Lines) :- trim_blank_text_lines_front(Lines0, Lines1), reverse(Lines1, RevLines1), trim_blank_text_lines_front(RevLines1, RevLines), reverse(RevLines, Lines), Lines = [_|_]. trim_blank_text_lines_front([Line|Lines0], Lines) :- blank_text_line(Line), !, trim_blank_text_lines_front(Lines0, Lines). trim_blank_text_lines_front(Lines, Lines). blank_text_line([]). blank_text_line([Code|Codes]) :- qr_text_space_code(Code), blank_text_line(Codes). qr_text_space_code(32). qr_text_space_code(9). qr_text_space_code(160). pad_text_lines(Lines0, Lines) :- max_text_line_width(Lines0, Width), maplist(pad_text_line(Width), Lines0, Lines). max_text_line_width([Line|Lines], Width) :- length(Line, LineWidth), max_text_line_width(Lines, LineWidth, Width). max_text_line_width([], Width, Width). max_text_line_width([Line|Lines], Width0, Width) :- length(Line, LineWidth), max_int(Width0, LineWidth, Width1), max_text_line_width(Lines, Width1, Width). pad_text_line(Width, Line0, Line) :- length(Line0, LineWidth), PaddingWidth is Width - LineWidth, spaces(PaddingWidth, Padding), append(Line0, Padding, Line). spaces(0, []). spaces(Count, [32|Codes]) :- Count > 0, Count1 is Count - 1, spaces(Count1, Codes). qr_text_lines_grid(Lines, Grid) :- qr_half_block_text_grid(Lines, Grid). qr_text_lines_grid(Lines, Grid) :- qr_wide_block_text_grid(Lines, Grid). qr_text_lines_grid(Lines, Grid) :- qr_full_block_text_grid(Lines, Grid). qr_half_block_text_grid(Lines, Grid) :- maplist(half_block_line_pair, Lines, RowPairs), append_row_pairs(RowPairs, Grid). half_block_line_pair(Line, [TopRow, BottomRow]) :- half_block_line_rows(Line, TopRow, BottomRow). half_block_line_rows([], [], []). half_block_line_rows([Code|Codes], [Top|TopBits], [Bottom|BottomBits]) :- qr_half_block_cell_bits(Code, Top, Bottom), half_block_line_rows(Codes, TopBits, BottomBits). qr_half_block_cell_bits(9608, 1, 1). qr_half_block_cell_bits(9600, 1, 0). qr_half_block_cell_bits(9604, 0, 1). qr_half_block_cell_bits(Code, 0, 0) :- qr_text_space_code(Code). append_row_pairs([], []). append_row_pairs([[TopRow, BottomRow]|RowPairs], [TopRow, BottomRow|Rows]) :- append_row_pairs(RowPairs, Rows). qr_wide_block_text_grid(Lines, Grid) :- maplist(qr_wide_block_line, Lines, Grid). qr_wide_block_line(Line0, Bits) :- qr_wide_line_codes(Line0, Line), qr_wide_block_line_pairs(Line, Bits). % Wide renderings use two columns per module. Copy-pasted border padding can % leave a single unmatched space on either side, so allow trimming one outer % whitespace code from the start and/or end before pairing the cells. qr_wide_line_codes(Line0, Line) :- maybe_drop_leading_space(Line0, Line1), maybe_drop_trailing_space(Line1, Line), even_length(Line). maybe_drop_leading_space([Code|Codes], Codes) :- qr_text_space_code(Code). maybe_drop_leading_space(Line, Line). maybe_drop_trailing_space(Line0, Line) :- append(Line, [Code], Line0), qr_text_space_code(Code). maybe_drop_trailing_space(Line, Line). even_length(Line) :- length(Line, Length), 0 is Length mod 2. qr_wide_block_line_pairs([], []). qr_wide_block_line_pairs([Code0,Code1|Codes], [Bit|Bits]) :- qr_wide_block_cell_bit(Code0, Code1, Bit), qr_wide_block_line_pairs(Codes, Bits). qr_wide_block_cell_bit(9608, 9608, 1). qr_wide_block_cell_bit(Code0, Code1, 0) :- qr_text_space_code(Code0), qr_text_space_code(Code1). qr_full_block_text_grid(Lines, Grid) :- maplist(qr_full_block_line, Lines, Grid). qr_full_block_line([], []). qr_full_block_line([Code|Codes], [Bit|Bits]) :- qr_full_block_cell_bit(Code, Bit), qr_full_block_line(Codes, Bits). qr_full_block_cell_bit(9608, 1). qr_full_block_cell_bit(Code, 0) :- qr_text_space_code(Code). qr_text_polarity_grid(Grid, Grid). qr_text_polarity_grid(Grid0, Grid) :- invert_binary_grid(Grid0, Grid). invert_binary_grid(Rows0, Rows) :- maplist(invert_binary_row, Rows0, Rows). invert_binary_row(Bits0, Bits) :- maplist(invert_binary_bit, Bits0, Bits). invert_binary_bit(0, 1). invert_binary_bit(1, 0). normalize_qr_text_grid(RawGrid, Grid) :- strip_zero_border(RawGrid, Grid), qr_input_grid(Grid), grid_size(Grid, Size), qr_matrix_size(Size). qr_matrix_size(Size) :- integer(Size), Size >= 21, 0 is (Size - 17) mod 4, Version is (Size - 17) // 4, Version >= 1, Version =< 40. strip_zero_border(Grid0, Grid) :- strip_zero_top(Grid0, Grid1), strip_zero_bottom(Grid1, Grid2), strip_zero_left(Grid2, Grid3), strip_zero_right(Grid3, Grid). strip_zero_top([Row|Rows], Grid) :- all_zero(Row), !, strip_zero_top(Rows, Grid). strip_zero_top(Grid, Grid). strip_zero_bottom(Grid0, Grid) :- reverse(Grid0, RevGrid0), strip_zero_top(RevGrid0, RevGrid), reverse(RevGrid, Grid). strip_zero_left(Grid0, Grid) :- all_zero_first_column(Grid0), !, remove_first_column(Grid0, Grid1), strip_zero_left(Grid1, Grid). strip_zero_left(Grid, Grid). all_zero_first_column([Row|Rows]) :- first_zero_cell(Row), all_zero_first_column_rows(Rows). all_zero_first_column_rows([]). all_zero_first_column_rows([Row|Rows]) :- first_zero_cell(Row), all_zero_first_column_rows(Rows). first_zero_cell([0|_Cells]). remove_first_column([], []). remove_first_column([[_Cell|Cells]|Rows], [Cells|RestRows]) :- remove_first_column(Rows, RestRows). strip_zero_right(Grid0, Grid) :- all_zero_last_column(Grid0), !, remove_last_column(Grid0, Grid1), strip_zero_right(Grid1, Grid). strip_zero_right(Grid, Grid). all_zero_last_column([Row|Rows]) :- last_zero_cell(Row), all_zero_last_column_rows(Rows). all_zero_last_column_rows([]). all_zero_last_column_rows([Row|Rows]) :- last_zero_cell(Row), all_zero_last_column_rows(Rows). last_zero_cell(Row) :- reverse(Row, [0|_Cells]). remove_last_column([], []). remove_last_column([Row|Rows], [TrimmedRow|TrimmedRows]) :- remove_last_cell(Row, TrimmedRow), remove_last_column(Rows, TrimmedRows). remove_last_cell(Row0, Row) :- reverse(Row0, [_Cell|RevRow]), reverse(RevRow, Row). % display_qr/1 renders the final 0/1 matrix with a quiet zone using Unicode % half blocks. Pairing two QR rows into one terminal row keeps modules close to % square, which scans better than a double-width full-block rendering. %% display_qr(+Grid) is det. %% display_qr_wide(+Grid) is det. %% qr_render(+Grid) is det. % % Render a binary QR matrix for terminal scanning. % % `display_qr/1` uses the compact half-block renderer. `display_qr_wide/1` % uses a double-width full-block form. `qr_render/1` is an alias for % `display_qr/1`. display_qr(Grid) :- qr_render_lines(Grid, Lines), write_lines(Lines), !. % display_qr_wide/1 renders each module as either "██" or two spaces. It is % less compact, but sometimes useful in terminals that do not render half % blocks cleanly. display_qr_wide(Grid) :- qr_render_lines_wide(Grid, Lines), write_lines(Lines), !. qr_render(Grid) :- display_qr(Grid), !. qr_render_lines(Grid, Lines) :- quiet_zone_grid(Grid, QuietGrid), render_half_rows(QuietGrid, Lines). qr_render_lines_wide(Grid, Lines) :- quiet_zone_grid(Grid, QuietGrid), maplist(render_wide_row, QuietGrid, Lines). quiet_zone_grid(Grid, QuietGrid) :- grid_size(Grid, Size), QuietWidth is Size + 8, zeros(QuietWidth, QuietRow), add_quiet_zone_rows(4, QuietRow, TopRows), maplist(add_quiet_zone_cols, Grid, MiddleRows), add_quiet_zone_rows(4, QuietRow, BottomRows), append(TopRows, MiddleRows, Rows1), append(Rows1, BottomRows, QuietGrid). %% Stream layer: relating text/segments to QR codewords % % This is the logical center of the QR payload pipeline. % % Encode direction: % text -> segments -> payload bits -> data codewords -> RS blocks % -> interleaved codewords % % Decode direction: % received codewords -> deinterleave -> RS repair -> payload bits % -> segments -> text % % The implementation intentionally keeps both directions adjacent so it is easy % to compare the two halves of the same relation. %% qr_stream_codewords(?Spec, ?Data, ?Codewords, -Stages) is nondet. % % Relate a QR payload and specification to an interleaved codeword stream. % % In the encode direction this builds the segment stream, payload bits, data % blocks, and ECC blocks. In the decode direction it deinterleaves the % received codewords, repairs them with Reed-Solomon, and parses the payload % back into QR items and user data. qr_stream_codewords(Spec, Data, Codewords, Stages) :- qr_spec_shape(Spec, Version, Level, Mode, _Mask), qr_input_data(Data), select_version(Version), prepare_stream_items(Version, Data, Mode, InputStages, Items, _Summary), select_level(Level), encode_data_words(Version, Level, Items, ItemStages, StreamBits, DataBits, DataWords), rs_blocks(Version, Level, Blocks), blocks_data_words(DataWords, Blocks, DataBlocks), blocks_ecc_words(DataBlocks, Blocks, EccBlocks), interleave_codewords(DataBlocks, EccBlocks, Codewords), % These stages follow the QR specification almost literally: segment % selection, per-segment bit encoding, terminator/padding, RS block split, % parity generation, and final interleaving. append(InputStages, [ stage(stream_items, Items), stage(item_stages, ItemStages), stage(stream_bits, StreamBits), stage(data_bits, DataBits), stage(data_codewords, DataWords), stage(data_blocks, DataBlocks), stage(ecc_blocks, EccBlocks), stage(codewords, Codewords) ], Stages). qr_stream_codewords(Spec, Data, Codewords, Stages) :- qr_spec_shape(Spec, Version, Level, Mode, _Mask), \+ qr_input_data(Data), qr_received_codeword_sequence(Codewords), select_version(Version), select_level(Level), rs_blocks(Version, Level, Blocks), deinterleave_codewords(Blocks, Codewords, ReceivedDataBlocks, ReceivedEccBlocks), correct_ecc_blocks(ReceivedDataBlocks, ReceivedEccBlocks, Blocks, DataBlocks, EccBlocks, Corrections), interleave_codewords(DataBlocks, EccBlocks, CorrectedCodewords), append_blocks(DataBlocks, DataWords), codewords_bits(DataWords, DataBits), parse_stream_items(Version, DataBits, Items, ItemStages, RestBits), items_summary_mode(Items, Summary), Mode = Summary, encode_data_words(Version, Level, Items, _ExpectedItemStages, StreamBits, _ExpectedDataBits, DataWords), decode_stream_data(Items, Data), % Decode-side stages distinguish what was received from what was repaired. Stages = [ stage(received_codewords, Codewords), stage(received_data_blocks, ReceivedDataBlocks), stage(received_ecc_blocks, ReceivedEccBlocks), stage(rs_corrections, Corrections), stage(stream_items, Items), stage(item_stages, ItemStages), stage(stream_bits, StreamBits), stage(trailing_bits, RestBits), stage(data_bits, DataBits), stage(data_codewords, DataWords), stage(data_blocks, DataBlocks), stage(ecc_blocks, EccBlocks), stage(codewords, CorrectedCodewords) ]. %% Matrix layer: relating codewords to the final QR grid % % This layer is the visual QR algorithm: % - build the fixed function patterns % - walk the zig-zag data path % - apply a mask pattern % - write format and version information % % In the reverse direction it reads the format information, removes the mask, % extracts the data path, and lifts partial bytes to codeword erasures. %% qr_grid_codewords(?Spec, ?Codewords, ?Grid, -Stages) is nondet. % % Relate interleaved codewords to the finished QR matrix. % % In the encode direction this builds the function patterns, places the data % bits, applies the selected mask, and writes format/version information. In % the decode direction it reads those same structures back out of a binary % grid and reconstructs the received codeword sequence. qr_grid_codewords(Spec, Codewords, Grid, Stages) :- qr_spec_shape(Spec, Version, Level, _Mode, Mask), qr_codeword_sequence(Codewords), select_mask(Mask), template_board(Version, FunctionBoard), data_positions(FunctionBoard, Positions), codewords_bits(Codewords, CodewordBits), fill_data_modules(CodewordBits, Positions, PlacementBits), place_data_bits(FunctionBoard, PlacementBits, FilledBoard), apply_mask(FilledBoard, Mask, MaskedBoard), format_bits(Level, Mask, FormatBits), place_format_bits(MaskedBoard, Version, FormatBits, BoardWithFormat), place_version_bits(BoardWithFormat, Version, FinalBoard), board_view(FunctionBoard, FunctionView), board_view(FilledBoard, FilledView), board_view(MaskedBoard, MaskedView), board_bits(FinalBoard, Grid), % The three intermediate board views are often the most useful educational % snapshots when learning how a QR matrix is constructed. Stages = [ stage(function_grid, FunctionView), stage(placed_grid, FilledView), stage(masked_grid, MaskedView), stage(format_bits, FormatBits), stage(grid, Grid) ]. qr_grid_codewords(Spec, Codewords, Grid, Stages) :- qr_spec_shape(Spec, Version, Level, _Mode, Mask), \+ qr_codeword_sequence(Codewords), qr_input_grid(Grid), grid_version(Grid, Version), read_format_bits(Grid, Level, Mask, FormatBits), template_board(Version, FunctionBoard), extract_data_bits(Grid, FunctionBoard, Mask, PlacementBits), total_codeword_count(Version, Level, TotalCodewords), CodewordBitCount is TotalCodewords * 8, split_at(CodewordBitCount, PlacementBits, CodewordBits, RemainderBits), bits_received_codewords(CodewordBits, Codewords), % Unknown modules become the atom erasure at the codeword layer. QR % Reed-Solomon operates on bytes, so this is the natural granularity for % partial recovery. Stages = [ stage(received_grid, Grid), stage(received_format_bits, FormatBits), stage(received_remainder_bits, RemainderBits), stage(extracted_codewords, Codewords) ]. %% Specification search and QR constraints % % The public relation backtracks over valid specifications. The choice order is % tuned so mask varies fastest and version slowest, which makes interactive % exploration in the Prolog REPL easier to follow. % % Specs use one canonical property-list shape: % % [version(Version), level(Level), mode(Mode), mask(Mask)] % % That keeps the structure readable and makes ad hoc inspection easy with % member/2. % % One practical Prolog nuance: plain member/2 on a fresh list is itself an % infinite generator, so a query like % % ?- member(version(1), Spec), qr("byakuren", Spec). % % can still diverge after the QR solutions are exhausted. To keep that style of % reasoning finite, first bound the shape with qr_spec/1: % % ?- qr_spec(Spec), member(version(1), Spec), qr("byakuren", Spec). % % or constrain one field directly with spec_property/2: % % ?- spec_property(version(1), Spec), qr("byakuren", Spec). % % qr_spec/1 is the bounded skeleton for spec reasoning. It is useful when you % want ordinary list reasoning with member/2 while still keeping the search % finite: % % ?- qr_spec(Spec), member(version(1), Spec), qr("byakuren", Spec). % ?- qr_spec(Spec), member(level(h), Spec), member(mask(0), Spec), % qr("byakuren", Spec, Grid). %% qr_spec(?Spec) is semidet. % % Canonical bounded skeleton for QR specs. % % This is the safe starting point when you want list-style reasoning over % specs with `member/2` without creating an open-ended list generator. qr_spec([version(_Version), level(_Level), mode(_Mode), mask(_Mask)]). qr_spec_shape(Spec, Version, Level, Mode, Mask) :- qr_spec(Spec), Spec = [version(Version), level(Level), mode(Mode), mask(Mask)]. % spec_property/2 is the direct relational interface for constraining one spec % field without going through member/2 on an open list. % % Examples: % ?- spec_property(version(1), Spec), qr("byakuren", Spec). % ?- spec_property(level(h), Spec), spec_property(mask(3), Spec), % qr("byakuren", Spec, Grid). % % The field-specific wrappers below are equivalent but sometimes read more % naturally in queries: % % ?- spec_version(Spec, 1), qr("byakuren", Spec). % ?- spec_level(Spec, h), spec_mode(Spec, byte), qr("byakuren", Spec, Grid). %% spec_property(?Property, ?Spec) is nondet. % % Relate one spec field to the canonical spec property list. % % `Property` is one of `version/1`, `level/1`, `mode/1`, or `mask/1`. spec_property(version(Version), Spec) :- qr_spec_shape(Spec, Version, _Level, _Mode, _Mask). spec_property(level(Level), Spec) :- qr_spec_shape(Spec, _Version, Level, _Mode, _Mask). spec_property(mode(Mode), Spec) :- qr_spec_shape(Spec, _Version, _Level, Mode, _Mask). spec_property(mask(Mask), Spec) :- qr_spec_shape(Spec, _Version, _Level, _Mode, Mask). select_level(Level) :- ( var(Level) -> level_order(Level) ; level_format_bits(Level, _FormatBits) ). level_order(h). level_order(q). level_order(m). level_order(l). select_version(Version) :- qr_between(1, 40, Version). select_mask(Mask) :- qr_between(0, 7, Mask). version_size(Version, Size) :- Size is 17 + Version * 4. grid_version(Grid, Version) :- grid_size(Grid, Size), Size >= 21, 0 is (Size - 17) mod 4, Version is (Size - 17) // 4, Version >= 1, Version =< 40. % Public geometry/capacity helpers. These are analysis predicates rather than % the main QR relation: they expose useful facts about a symbol without having % to inspect low-level stages manually. %% qr_version_size(?Version, ?Size) is nondet. %% qr_grid_size(+Grid, -Size) is semidet. %% qr_grid_version(+Grid, -Version) is semidet. % % Small geometry helpers for specs and finished matrices. qr_version_size(Version, Size) :- select_version(Version), version_size(Version, Size). qr_grid_size(Grid, Size) :- grid_size(Grid, Size). qr_grid_version(Grid, Version) :- grid_version(Grid, Version). %% qr_analysis(?Input, -Analysis) is nondet. % % Bundle the common derived views of one QR symbol into a property list. qr_analysis(Input, Analysis) :- qr_input_data(Input), qr_code(Input, Grid, Spec, _Stages), qr_codewords(Input, Spec, ReceivedCodewords, Codewords), qr_analysis_properties(Input, Spec, Grid, ReceivedCodewords, Codewords, Analysis). qr_analysis(InputGrid, Analysis) :- qr_input_grid(InputGrid), copy_term(InputGrid, ReceivedGrid), qr_code(Data, InputGrid, Spec, Stages), member(stage(grid, Grid), Stages), qr_codewords(ReceivedGrid, Spec, ReceivedCodewords, Codewords), qr_analysis_properties(Data, Spec, Grid, ReceivedCodewords, Codewords, Analysis). qr_analysis_properties(Data, Spec, Grid, ReceivedCodewords, Codewords, [ data(Data), spec(Spec), grid(Grid), size(Size), capacity(Capacity), penalty(Penalty), penalty_breakdown(Breakdown), received_codewords(ReceivedCodewords), codewords(Codewords), mask_penalties(MaskPenalties) ]) :- qr_grid_size(Grid, Size), qr_capacity(Spec, Capacity), qr_penalty(Grid, Penalty), qr_penalty_breakdown(Grid, Breakdown), analysis_mask_penalties(Data, Spec, MaskPenalties). analysis_mask_penalties(Data, Spec, MaskPenalties) :- spec_version(Spec, Version), spec_level(Spec, Level), spec_mode(Spec, Mode), qr_mask_penalties(Data, [ version(Version), level(Level), mode(Mode), mask(_Mask) ], MaskPenalties). %% qr_mask_penalties(+Data, ?Spec, -MaskPenalties) is nondet. % % Compare mask scores for one fixed version/level/mode family. qr_mask_penalties(Data, Spec, MaskPenalties) :- qr_input_data(Data), qr_spec_shape(Spec, Version, Level, Mode, MaskConstraint), qr_stream_codewords(Spec, Data, Codewords, _Stages), mask_penalties_for_codewords(Version, Level, Mode, Codewords, MaskConstraint, MaskPenalties). mask_penalties_for_codewords(Version, Level, Mode, Codewords, MaskConstraint, MaskPenalties) :- findall(mask_penalty(Mask, Penalty), ( MaskConstraint = Mask, select_mask(Mask), MaskSpec = [ version(Version), level(Level), mode(Mode), mask(Mask) ], qr_grid_codewords(MaskSpec, Codewords, Grid, _GridStages), qr_penalty(Grid, Penalty) ), MaskPenalties). %% qr_codewords(?Input, ?Spec, -ReceivedCodewords, -Codewords) is nondet. % % Expose received and corrected codewords directly. qr_codewords(Data, Spec, ReceivedCodewords, Codewords) :- qr_input_data(Data), qr_spec_shape(Spec, _Version, _Level, _Mode, _Mask), qr_stream_codewords(Spec, Data, Codewords, _Stages), ReceivedCodewords = Codewords. qr_codewords(Grid, Spec, ReceivedCodewords, Codewords) :- qr_input_grid(Grid), qr_spec_shape(Spec, _Version, _Level, _Mode, _Mask), qr_grid_codewords(Spec, ReceivedCodewords, Grid, _ExtractStages), qr_stream_codewords(Spec, _Data, ReceivedCodewords, StreamStages), member(stage(codewords, Codewords), StreamStages). %% qr_capacity(?Spec, -Capacity) is nondet. % % Report the structural capacity implied by a spec's version and EC level. qr_capacity(Spec, Capacity) :- qr_spec_shape(Spec, Version, Level, _Mode, _Mask), select_version(Version), select_level(Level), version_size(Version, Size), total_data_word_count(Version, Level, DataCodewords), total_codeword_count(Version, Level, TotalCodewords), EccCodewords is TotalCodewords - DataCodewords, DataBits is DataCodewords * 8, Capacity = [ size(Size), total_codewords(TotalCodewords), data_codewords(DataCodewords), data_bits(DataBits), ecc_codewords(EccCodewords) ]. version_group(Version, small) :- Version =< 9. version_group(Version, medium) :- Version >= 10, Version =< 26. version_group(Version, large) :- Version >= 27. %% Segment and mode support % % QR payloads are a stream of typed segments. Simple text usually becomes a % single numeric/alphanumeric/byte/kanji segment, or an ECI+byte pair for % UTF-8. The same machinery also handles explicit qr_data([...]) streams with % ECI, FNC1, and structured append. mode_indicator(terminator, [0,0,0,0]). mode_indicator(numeric, [0,0,0,1]). mode_indicator(alphanumeric, [0,0,1,0]). mode_indicator(structured_append, [0,0,1,1]). mode_indicator(byte, [0,1,0,0]). mode_indicator(fnc1_first, [0,1,0,1]). mode_indicator(eci, [0,1,1,1]). mode_indicator(kanji, [1,0,0,0]). mode_indicator(fnc1_second, [1,0,0,1]). mode_order(numeric). mode_order(alphanumeric). mode_order(kanji). mode_order(byte). mode_order(utf8). count_bit_length(Version, Mode, Width) :- version_group(Version, Group), count_bit_length_group(Group, Mode, Width). count_bit_length_group(small, numeric, 10). count_bit_length_group(small, alphanumeric, 9). count_bit_length_group(small, byte, 8). count_bit_length_group(small, kanji, 8). count_bit_length_group(medium, numeric, 12). count_bit_length_group(medium, alphanumeric, 11). count_bit_length_group(medium, byte, 16). count_bit_length_group(medium, kanji, 10). count_bit_length_group(large, numeric, 14). count_bit_length_group(large, alphanumeric, 13). count_bit_length_group(large, byte, 16). count_bit_length_group(large, kanji, 12). prepare_stream_items(_Version, qr_data(RawItems), Mode, InputStages, Items, Summary) :- normalize_qr_items(RawItems, Items), items_summary_mode(Items, Summary), Mode = Summary, InputStages = [stage(input, qr_data(RawItems))]. prepare_stream_items(Version, Data, Mode, InputStages, Items, Summary) :- text_codes(Data, Codes), ( var(Mode) -> select_text_items(Codes, Mode, Items, Summary) ; Mode == segments -> best_text_items_for_version(Version, Data, Items), items_summary_mode(Items, Summary), Summary == segments ; select_text_items(Codes, Mode, Items, Summary) ), InputStages = [ stage(input, Data), stage(text_codes, Codes) ]. select_text_items(Codes, Mode, Items, Summary) :- ( var(Mode) -> mode_order(Summary), text_mode_items(Codes, Summary, Items), Mode = Summary ; Summary = Mode, text_mode_items(Codes, Summary, Items) ). text_mode_items(Codes, numeric, [numeric(Codes)]) :- Codes \= [], digits_codes(Codes, _Digits). text_mode_items(Codes, alphanumeric, [alphanumeric(Codes)]) :- Codes \= [], alphanumeric_codes(Codes). text_mode_items(Codes, kanji, [kanji(Codes)]) :- Codes \= [], kanji_codes(Codes). text_mode_items(Codes, byte, [byte(Codes)]) :- valid_bytes(Codes). text_mode_items(Codes, utf8, [eci(26), byte(Bytes)]) :- utf8_bytes_from_codes(Codes, Bytes). % best_text_items_for_version/3 is used by qr/1..3 to search for a shorter % mixed-mode segmentation than the simple whole-input mode choices above. % qr_code/* remains relational and still enumerates the direct mode choices; % this helper is only for the deterministic "best QR" wrapper layer. best_text_items_for_version(Version, Text, Items) :- text_codes(Text, Codes), Codes \= [], text_suffixes(Codes, Suffixes), best_text_suffix_entries(Version, Suffixes, [entry(DefaultBest, _Utf8Best)|_Entries]), DefaultBest = best(_Cost, _SegmentCount, Items). text_suffixes([], [[]]). text_suffixes([Code|Codes], [[Code|Codes]|Suffixes]) :- text_suffixes(Codes, Suffixes). best_text_suffix_entries(_Version, [[]], [entry(best(0, 0, []), best(0, 0, []))]). best_text_suffix_entries(Version, [Codes|Suffixes], [entry(DefaultBest, Utf8Best)|Entries]) :- Codes \= [], best_text_suffix_entries(Version, Suffixes, Entries), best_text_state(Version, Codes, default, Entries, DefaultBest), best_text_state(Version, Codes, utf8, Entries, Utf8Best). best_text_state(Version, Codes, ByteState, FutureEntries, Best) :- findall(Candidate, best_text_candidate(Version, Codes, ByteState, FutureEntries, Candidate), Candidates), Candidates = [Candidate|RestCandidates], best_text_candidate(RestCandidates, Candidate, Best). best_text_candidate([], Best, Best). best_text_candidate([Candidate|Candidates], Best0, Best) :- better_text_candidate(Candidate, Best0), !, best_text_candidate(Candidates, Candidate, Best). best_text_candidate([_Candidate|Candidates], Best0, Best) :- best_text_candidate(Candidates, Best0, Best). better_text_candidate(best(Cost, SegmentCount, Items), best(Cost0, SegmentCount0, Items0)) :- key(Cost, SegmentCount, Items) @< key(Cost0, SegmentCount0, Items0). best_text_candidate(Version, Codes, ByteState, FutureEntries, best(Cost, SegmentCount, Items)) :- segmentation_prefix(Codes, ByteState, PrefixItems, ConsumedCount), byte_state_stream(ByteState, StreamState0), items_bits(Version, PrefixItems, StreamState0, StreamState, _ItemStages, PrefixBits), stream_byte_state(StreamState, NextByteState), nth1(ConsumedCount, FutureEntries, FutureEntry), entry_state_best(NextByteState, FutureEntry, best(FutureCost, FutureSegmentCount, FutureItems)), length(PrefixBits, PrefixCost), length(PrefixItems, PrefixSegmentCount), Cost is PrefixCost + FutureCost, SegmentCount is PrefixSegmentCount + FutureSegmentCount, append(PrefixItems, FutureItems, Items). entry_state_best(default, entry(DefaultBest, _Utf8Best), DefaultBest). entry_state_best(utf8, entry(_DefaultBest, Utf8Best), Utf8Best). byte_state_stream(default, stream_state(none, default)). byte_state_stream(utf8, stream_state(none, 26)). stream_byte_state(stream_state(_Fnc1, 26), utf8) :- !. stream_byte_state(stream_state(_Fnc1, default), default) :- !. stream_byte_state(stream_state(_Fnc1, 3), default) :- !. stream_byte_state(stream_state(_Fnc1, _Assignment), default). segmentation_prefix(Codes, _ByteState, [numeric(Prefix)], ConsumedCount) :- numeric_prefix(Codes, Prefix, ConsumedCount). segmentation_prefix(Codes, _ByteState, [alphanumeric(Prefix)], ConsumedCount) :- alphanumeric_prefix(Codes, Prefix, ConsumedCount). segmentation_prefix(Codes, _ByteState, [kanji(Prefix)], ConsumedCount) :- kanji_prefix(Codes, Prefix, ConsumedCount). segmentation_prefix(Codes, default, [byte(Prefix)], ConsumedCount) :- byte_prefix(Codes, Prefix, ConsumedCount). segmentation_prefix(Codes, utf8, [byte(Bytes)], ConsumedCount) :- utf8_prefix(Codes, Prefix, ConsumedCount), utf8_bytes_from_codes(Prefix, Bytes). segmentation_prefix(Codes, default, [eci(26), byte(Bytes)], ConsumedCount) :- utf8_prefix(Codes, Prefix, ConsumedCount), utf8_bytes_from_codes(Prefix, Bytes). segmentation_prefix(Codes, utf8, [eci(3), byte(Prefix)], ConsumedCount) :- byte_prefix(Codes, Prefix, ConsumedCount). numeric_prefix([Code|_Codes], [Code], 1) :- digit_code(Code, _Digit). numeric_prefix([Code|Codes], [Code|Prefix], Count) :- digit_code(Code, _Digit), numeric_prefix(Codes, Prefix, Count0), Count is Count0 + 1. alphanumeric_prefix([Code|_Codes], [Code], 1) :- alphanumeric_value(Code, _Value). alphanumeric_prefix([Code|Codes], [Code|Prefix], Count) :- alphanumeric_value(Code, _Value), alphanumeric_prefix(Codes, Prefix, Count0), Count is Count0 + 1. kanji_prefix([Code|_Codes], [Code], 1) :- kanji_qr(Code, _Value). kanji_prefix([Code|Codes], [Code|Prefix], Count) :- kanji_qr(Code, _Value), kanji_prefix(Codes, Prefix, Count0), Count is Count0 + 1. byte_prefix([Code|_Codes], [Code], 1) :- integer(Code), Code >= 0, Code =< 255. byte_prefix([Code|Codes], [Code|Prefix], Count) :- integer(Code), Code >= 0, Code =< 255, byte_prefix(Codes, Prefix, Count0), Count is Count0 + 1. utf8_prefix([Code|_Codes], [Code], 1) :- unicode_scalar_value(Code). utf8_prefix([Code|Codes], [Code|Prefix], Count) :- unicode_scalar_value(Code), utf8_prefix(Codes, Prefix, Count0), Count is Count0 + 1. normalize_qr_items([], []). normalize_qr_items([RawItem|RawItems], Items) :- normalize_qr_item(RawItem, ItemList), normalize_qr_items(RawItems, RestItems), append(ItemList, RestItems, Items). normalize_qr_item(numeric(Text), [numeric(Codes)]) :- text_codes(Text, Codes), Codes \= [], !. normalize_qr_item(alphanumeric(Text), [alphanumeric(Codes)]) :- text_codes(Text, Codes), Codes \= [], !. normalize_qr_item(byte(Bytes0), [byte(Bytes)]) :- bytes_term(Bytes0, Bytes), !. normalize_qr_item(latin1(Text), [byte(Bytes)]) :- text_codes(Text, Bytes), valid_bytes(Bytes), !. normalize_qr_item(ascii(Text), [eci(27), byte(Bytes)]) :- text_codes(Text, Codes), encoding_codes_bytes(ascii, Codes, Bytes), !. normalize_qr_item(utf8(Text), [eci(26), byte(Bytes)]) :- text_codes(Text, Codes), encoding_codes_bytes(utf8, Codes, Bytes), !. normalize_qr_item(utf16be(Text), [eci(25), byte(Bytes)]) :- text_codes(Text, Codes), encoding_codes_bytes(utf16be, Codes, Bytes), !. normalize_qr_item(eci_text(Assignment, Text), [eci(Assignment), byte(Bytes)]) :- eci_text_encoding(Assignment, Encoding), text_codes(Text, Codes), encoding_codes_bytes(Encoding, Codes, Bytes), !. normalize_qr_item(kanji(Text), [kanji(Codes)]) :- text_codes(Text, Codes), Codes \= [], kanji_codes(Codes), !. normalize_qr_item(eci(Assignment), [eci(Assignment)]) :- valid_eci_assignment(Assignment), !. normalize_qr_item(fnc1(first), [fnc1(first)]) :- !. normalize_qr_item(fnc1(second, Indicator0), [fnc1(second, Indicator)]) :- indicator_byte(Indicator0, Indicator), !. normalize_qr_item(structured_append(Index, Total, Parity), [structured_append(Index, Total, Parity)]) :- valid_structured_append(Index, Total, Parity), !. normalize_qr_item(Item, [Item]) :- normalized_stream_item(Item). normalized_stream_item(numeric(Codes)) :- proper_list(Codes). normalized_stream_item(alphanumeric(Codes)) :- proper_list(Codes). normalized_stream_item(byte(Bytes)) :- valid_bytes(Bytes). normalized_stream_item(kanji(Codes)) :- proper_list(Codes). normalized_stream_item(eci(Assignment)) :- valid_eci_assignment(Assignment). normalized_stream_item(fnc1(first)). normalized_stream_item(fnc1(second, Indicator)) :- integer(Indicator), Indicator >= 0, Indicator =< 255. normalized_stream_item(structured_append(Index, Total, Parity)) :- valid_structured_append(Index, Total, Parity). bytes_term(Bytes, Bytes) :- proper_list(Bytes), valid_bytes(Bytes), !. bytes_term(Text, Bytes) :- text_codes(Text, Bytes), valid_bytes(Bytes). indicator_byte(Indicator, Indicator) :- integer(Indicator), Indicator >= 0, Indicator =< 255, !. indicator_byte(IndicatorText, Indicator) :- text_codes(IndicatorText, [Indicator]). valid_eci_assignment(Assignment) :- integer(Assignment), Assignment >= 0, Assignment =< 999999. valid_structured_append(Index, Total, Parity) :- integer(Index), Index >= 0, Index =< 15, integer(Total), Total >= 0, Total =< 15, integer(Parity), Parity >= 0, Parity =< 255. items_summary_mode([numeric(_)], numeric) :- !. items_summary_mode([alphanumeric(_)], alphanumeric) :- !. items_summary_mode([kanji(_)], kanji) :- !. items_summary_mode([byte(_)], byte) :- !. items_summary_mode([eci(26), byte(Bytes)], utf8) :- encoding_bytes_codes(utf8, Bytes, _Codes), !. items_summary_mode(_Items, segments). digits_codes([], []). digits_codes([Code|Codes], [Digit|Digits]) :- digit_code(Code, Digit), digits_codes(Codes, Digits). digit_code(Code, Digit) :- integer(Code), Code >= 0'0, Code =< 0'9, Digit is Code - 0'0. alphanumeric_codes([]). alphanumeric_codes([Code|Codes]) :- alphanumeric_value(Code, _Value), alphanumeric_codes(Codes). alphanumeric_table("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:"). alphanumeric_value(Code, Value) :- integer(Code), !, char_code(Char, Code), alphanumeric_char_value(Char, Value). alphanumeric_value(Code, Value) :- var(Code), !, alphanumeric_char_value(Char, Value), char_code(Char, Code). alphanumeric_value(Code, Value) :- atom(Code), atom_length(Code, 1), !, alphanumeric_char_value(Code, Value). alphanumeric_value(Code, Value) :- char_code(Char, Code), alphanumeric_char_value(Char, Value). alphanumeric_char_value(Code, Value) :- alphanumeric_table(Table), nth0(Value, Table, Code). valid_bytes([]). valid_bytes([Code|Codes]) :- integer(Code), Code >= 0, Code =< 255, valid_bytes(Codes). ascii_codes([]). ascii_codes([Code|Codes]) :- integer(Code), Code >= 0, Code =< 127, ascii_codes(Codes). encoding_codes_bytes(latin1, Codes, Bytes) :- valid_bytes(Codes), Bytes = Codes. encoding_codes_bytes(ascii, Codes, Bytes) :- ascii_codes(Codes), Bytes = Codes. encoding_codes_bytes(utf8, Codes, Bytes) :- utf8_bytes_from_codes(Codes, Bytes). encoding_codes_bytes(utf16be, Codes, Bytes) :- utf16be_bytes_from_codes(Codes, Bytes). encoding_bytes_codes(latin1, Bytes, Codes) :- valid_bytes(Bytes), Codes = Bytes. encoding_bytes_codes(ascii, Bytes, Codes) :- ascii_codes(Bytes), Codes = Bytes. encoding_bytes_codes(utf8, Bytes, Codes) :- utf8_bytes_codes(Bytes, Codes). encoding_bytes_codes(utf16be, Bytes, Codes) :- utf16be_bytes_codes(Bytes, Codes). kanji_codes([]). kanji_codes([Code|Codes]) :- kanji_qr(Code, _Value), kanji_codes(Codes). %% Segment payload encoding and parsing % % encode_data_words/7 performs the byte-level QR payload rules: % - append a terminator % - pad to the next byte boundary % - append alternating 236/17 pad bytes until the version/level capacity is % exactly filled encode_data_words(Version, Level, Items, ItemStages, StreamBits, DataBits, DataWords) :- items_bits(Version, Items, stream_state(none, default), _FinalState, ItemStages, StreamBits), total_data_word_count(Version, Level, DataWordCount), fill_data_capacity(StreamBits, DataWordCount, DataBits, DataWords). fill_data_capacity(SegmentBits, DataWordCount, DataBits, DataWords) :- CapacityBits is DataWordCount * 8, length(SegmentBits, SegmentLength), SegmentLength =< CapacityBits, TerminatorLength0 is CapacityBits - SegmentLength, min_int(4, TerminatorLength0, TerminatorLength), zeros(TerminatorLength, TerminatorBits), append(SegmentBits, TerminatorBits, WithTerminator), length(WithTerminator, TerminatorLength1), BytePadding is (8 - (TerminatorLength1 mod 8)) mod 8, zeros(BytePadding, BytePaddingBits), append(WithTerminator, BytePaddingBits, ByteAlignedBits), bits_codewords(ByteAlignedBits, PartialWords), fill_pad_words(PartialWords, DataWordCount, DataWords), codewords_bits(DataWords, DataBits). fill_pad_words(Words, Count, FinalWords) :- fill_pad_words(Words, Count, 0, FinalWords). fill_pad_words(Words, Count, _PadIndex, Words) :- length(Words, Count), !. fill_pad_words(Words, Count, PadIndex, FinalWords) :- length(Words, Length), Length < Count, pad_word(PadIndex, PadWord), append(Words, [PadWord], Words1), PadIndex1 is PadIndex + 1, fill_pad_words(Words1, Count, PadIndex1, FinalWords). pad_word(Index, Word) :- integer(Index), Index >= 0, Parity is Index mod 2, ( Parity =:= 0 -> Word = 236 ; Word = 17 ). items_bits(_Version, [], State, State, [], []). items_bits(Version, [Item|Items], State0, State, [ItemStage|ItemStages], Bits) :- item_bits(Version, Item, State0, State1, ItemStage, ItemBits), items_bits(Version, Items, State1, State, ItemStages, RestBits), append(ItemBits, RestBits, Bits). item_bits(Version, numeric(Codes), State, State, item_stage(numeric(Codes), ModeBits, CountBits, PayloadBits), Bits) :- digits_codes(Codes, _Digits), mode_indicator(numeric, ModeBits), length(Codes, Count), count_bit_length(Version, numeric, CountWidth), int_bits(Count, CountWidth, CountBits), payload_bits(numeric, Codes, PayloadBits), append(ModeBits, CountBits, PrefixBits), append(PrefixBits, PayloadBits, Bits). item_bits(Version, alphanumeric(Codes), stream_state(Fnc1, Eci), stream_state(Fnc1, Eci), item_stage(alphanumeric(Codes), ModeBits, CountBits, PayloadBits), Bits) :- fnc1_alphanumeric_encode(Fnc1, Codes, EncodedCodes), alphanumeric_codes(EncodedCodes), mode_indicator(alphanumeric, ModeBits), length(EncodedCodes, Count), count_bit_length(Version, alphanumeric, CountWidth), int_bits(Count, CountWidth, CountBits), payload_bits(alphanumeric, EncodedCodes, PayloadBits), append(ModeBits, CountBits, PrefixBits), append(PrefixBits, PayloadBits, Bits). item_bits(Version, byte(Bytes), State, State, item_stage(byte(Bytes), ModeBits, CountBits, PayloadBits), Bits) :- valid_bytes(Bytes), mode_indicator(byte, ModeBits), length(Bytes, Count), count_bit_length(Version, byte, CountWidth), int_bits(Count, CountWidth, CountBits), payload_bits(byte, Bytes, PayloadBits), append(ModeBits, CountBits, PrefixBits), append(PrefixBits, PayloadBits, Bits). item_bits(Version, kanji(Codes), State, State, item_stage(kanji(Codes), ModeBits, CountBits, PayloadBits), Bits) :- kanji_codes(Codes), mode_indicator(kanji, ModeBits), length(Codes, Count), count_bit_length(Version, kanji, CountWidth), int_bits(Count, CountWidth, CountBits), payload_bits(kanji, Codes, PayloadBits), append(ModeBits, CountBits, PrefixBits), append(PrefixBits, PayloadBits, Bits). item_bits(_Version, eci(Assignment), stream_state(Fnc1, _OldEci), stream_state(Fnc1, Assignment), item_stage(eci(Assignment), ModeBits, [], PayloadBits), Bits) :- valid_eci_assignment(Assignment), mode_indicator(eci, ModeBits), eci_payload_bits(Assignment, PayloadBits), append(ModeBits, PayloadBits, Bits). item_bits(_Version, fnc1(first), stream_state(_OldFnc1, Eci), stream_state(first, Eci), item_stage(fnc1(first), ModeBits, [], []), ModeBits) :- mode_indicator(fnc1_first, ModeBits). item_bits(_Version, fnc1(second, Indicator), stream_state(_OldFnc1, Eci), stream_state(second(Indicator), Eci), item_stage(fnc1(second, Indicator), ModeBits, [], PayloadBits), Bits) :- integer(Indicator), Indicator >= 0, Indicator =< 255, mode_indicator(fnc1_second, ModeBits), int_bits(Indicator, 8, PayloadBits), append(ModeBits, PayloadBits, Bits). item_bits(_Version, structured_append(Index, Total, Parity), State, State, item_stage(structured_append(Index, Total, Parity), ModeBits, [], PayloadBits), Bits) :- valid_structured_append(Index, Total, Parity), mode_indicator(structured_append, ModeBits), int_bits(Index, 4, IndexBits), int_bits(Total, 4, TotalBits), int_bits(Parity, 8, ParityBits), append(IndexBits, TotalBits, Bits0), append(Bits0, ParityBits, PayloadBits), append(ModeBits, PayloadBits, Bits). payload_bits(byte, Codes, Bits) :- bytes_bits(Codes, Bits). payload_bits(numeric, Codes, Bits) :- digits_codes(Codes, Digits), numeric_payload_bits(Digits, Bits). payload_bits(alphanumeric, Codes, Bits) :- alphanumeric_payload_bits(Codes, Bits). payload_bits(kanji, Codes, Bits) :- kanji_payload_bits(Codes, Bits). bytes_bits([], []). bytes_bits([Code|Codes], Bits) :- int_bits(Code, 8, HeadBits), bytes_bits(Codes, TailBits), append(HeadBits, TailBits, Bits). numeric_payload_bits([], []). numeric_payload_bits([A,B,C|Digits], Bits) :- Value is A * 100 + B * 10 + C, int_bits(Value, 10, HeadBits), numeric_payload_bits(Digits, TailBits), append(HeadBits, TailBits, Bits). numeric_payload_bits([A,B], Bits) :- Value is A * 10 + B, int_bits(Value, 7, Bits). numeric_payload_bits([A], Bits) :- int_bits(A, 4, Bits). alphanumeric_payload_bits([], []). alphanumeric_payload_bits([A,B|Codes], Bits) :- alphanumeric_value(A, ValueA), alphanumeric_value(B, ValueB), Value is ValueA * 45 + ValueB, int_bits(Value, 11, HeadBits), alphanumeric_payload_bits(Codes, TailBits), append(HeadBits, TailBits, Bits). alphanumeric_payload_bits([A], Bits) :- alphanumeric_value(A, ValueA), int_bits(ValueA, 6, Bits). kanji_payload_bits([], []). kanji_payload_bits([Code|Codes], Bits) :- kanji_qr(Code, Value), int_bits(Value, 13, HeadBits), kanji_payload_bits(Codes, TailBits), append(HeadBits, TailBits, Bits). parse_payload_bits(byte, Count, Bits0, Codes, PayloadBits, Rest) :- byte_codes_bits(Count, Bits0, Codes, PayloadBits, Rest). parse_payload_bits(numeric, Count, Bits0, Codes, PayloadBits, Rest) :- numeric_codes_bits(Count, Bits0, Codes, PayloadBits, Rest). parse_payload_bits(alphanumeric, Count, Bits0, Codes, PayloadBits, Rest) :- alphanumeric_codes_bits(Count, Bits0, Codes, PayloadBits, Rest). parse_payload_bits(kanji, Count, Bits0, Codes, PayloadBits, Rest) :- kanji_codes_bits(Count, Bits0, Codes, PayloadBits, Rest). byte_codes_bits(0, Bits, [], [], Bits). byte_codes_bits(Count, Bits0, [Code|Codes], PayloadBits, Rest) :- Count > 0, split_at(8, Bits0, ByteBits, Bits1), bits_int(ByteBits, Code), Count1 is Count - 1, byte_codes_bits(Count1, Bits1, Codes, MorePayloadBits, Rest), append(ByteBits, MorePayloadBits, PayloadBits). numeric_codes_bits(0, Bits, [], [], Bits). numeric_codes_bits(Count, Bits0, Codes, PayloadBits, Rest) :- Count >= 3, split_at(10, Bits0, GroupBits, Bits1), bits_int(GroupBits, Value), Value < 1000, int_digits(Value, 3, Digits), digits_to_codes(Digits, Codes0), Count1 is Count - 3, numeric_codes_bits(Count1, Bits1, Codes1, MorePayloadBits, Rest), append(Codes0, Codes1, Codes), append(GroupBits, MorePayloadBits, PayloadBits). numeric_codes_bits(2, Bits0, Codes, PayloadBits, Rest) :- split_at(7, Bits0, GroupBits, Rest), bits_int(GroupBits, Value), Value < 100, int_digits(Value, 2, Digits), digits_to_codes(Digits, Codes), PayloadBits = GroupBits. numeric_codes_bits(1, Bits0, Codes, PayloadBits, Rest) :- split_at(4, Bits0, GroupBits, Rest), bits_int(GroupBits, Value), Value < 10, int_digits(Value, 1, Digits), digits_to_codes(Digits, Codes), PayloadBits = GroupBits. alphanumeric_codes_bits(0, Bits, [], [], Bits). alphanumeric_codes_bits(Count, Bits0, [CodeA,CodeB|Codes], PayloadBits, Rest) :- Count >= 2, split_at(11, Bits0, GroupBits, Bits1), bits_int(GroupBits, Value), ValueA is Value div 45, ValueB is Value mod 45, alphanumeric_value(CodeA, ValueA), alphanumeric_value(CodeB, ValueB), Count1 is Count - 2, alphanumeric_codes_bits(Count1, Bits1, Codes, MorePayloadBits, Rest), append(GroupBits, MorePayloadBits, PayloadBits). alphanumeric_codes_bits(1, Bits0, [CodeA], PayloadBits, Rest) :- split_at(6, Bits0, GroupBits, Rest), bits_int(GroupBits, ValueA), alphanumeric_value(CodeA, ValueA), PayloadBits = GroupBits. kanji_codes_bits(0, Bits, [], [], Bits). kanji_codes_bits(Count, Bits0, [Code|Codes], PayloadBits, Rest) :- Count > 0, split_at(13, Bits0, GroupBits, Bits1), bits_int(GroupBits, Value), kanji_qr(Code, Value), Count1 is Count - 1, kanji_codes_bits(Count1, Bits1, Codes, MorePayloadBits, Rest), append(GroupBits, MorePayloadBits, PayloadBits). eci_payload_bits(Assignment, Bits) :- Assignment < 128, !, int_bits(Assignment, 8, Bits). eci_payload_bits(Assignment, Bits) :- Assignment < 16384, !, Value is 32768 \/ Assignment, int_bits(Value, 16, Bits). eci_payload_bits(Assignment, Bits) :- Assignment =< 999999, Value is 12582912 \/ Assignment, int_bits(Value, 24, Bits). parse_stream_items(Version, Bits, Items, ItemStages, RestBits) :- parse_stream_items(Version, Bits, stream_state(none, default), _FinalState, Items, ItemStages, RestBits). parse_stream_items(_Version, [], State, State, [], [], []). parse_stream_items(_Version, Bits, State, State, [], [], Bits) :- stream_terminator_bits(Bits), !. parse_stream_items(Version, Bits0, State0, State, [Item|Items], [ItemStage|ItemStages], RestBits) :- split_at(4, Bits0, ModeBits, Bits1), mode_indicator(Kind, ModeBits), Kind \== terminator, parse_stream_item(Version, Kind, Bits1, State0, State1, Item, CountBits, PayloadBits, Bits2), ItemStage = item_stage(Item, ModeBits, CountBits, PayloadBits), parse_stream_items(Version, Bits2, State1, State, Items, ItemStages, RestBits). stream_terminator_bits([]). stream_terminator_bits(Bits) :- starts_with_zero_bits(Bits, 4), !. stream_terminator_bits(Bits) :- length(Bits, Length), Length < 4, all_zero(Bits). starts_with_zero_bits(_Bits, 0). starts_with_zero_bits([0|Bits], Count) :- Count > 0, Count1 is Count - 1, starts_with_zero_bits(Bits, Count1). parse_stream_item(Version, numeric, Bits0, State, State, numeric(Codes), CountBits, PayloadBits, Rest) :- count_bit_length(Version, numeric, CountWidth), split_at(CountWidth, Bits0, CountBits, Bits1), bits_int(CountBits, Count), parse_payload_bits(numeric, Count, Bits1, Codes, PayloadBits, Rest). parse_stream_item(Version, alphanumeric, Bits0, stream_state(Fnc1, Eci), stream_state(Fnc1, Eci), alphanumeric(Codes), CountBits, PayloadBits, Rest) :- count_bit_length(Version, alphanumeric, CountWidth), split_at(CountWidth, Bits0, CountBits, Bits1), bits_int(CountBits, Count), parse_payload_bits(alphanumeric, Count, Bits1, EncodedCodes, PayloadBits, Rest), fnc1_alphanumeric_decode(Fnc1, EncodedCodes, Codes). parse_stream_item(Version, byte, Bits0, State, State, byte(Bytes), CountBits, PayloadBits, Rest) :- count_bit_length(Version, byte, CountWidth), split_at(CountWidth, Bits0, CountBits, Bits1), bits_int(CountBits, Count), parse_payload_bits(byte, Count, Bits1, Bytes, PayloadBits, Rest). parse_stream_item(Version, kanji, Bits0, State, State, kanji(Codes), CountBits, PayloadBits, Rest) :- count_bit_length(Version, kanji, CountWidth), split_at(CountWidth, Bits0, CountBits, Bits1), bits_int(CountBits, Count), parse_payload_bits(kanji, Count, Bits1, Codes, PayloadBits, Rest). parse_stream_item(_Version, eci, Bits0, stream_state(Fnc1, _OldEci), stream_state(Fnc1, Assignment), eci(Assignment), [], PayloadBits, Rest) :- parse_eci_payload_bits(Bits0, Assignment, PayloadBits, Rest). parse_stream_item(_Version, fnc1_first, Bits, stream_state(_OldFnc1, Eci), stream_state(first, Eci), fnc1(first), [], [], Bits). parse_stream_item(_Version, fnc1_second, Bits0, stream_state(_OldFnc1, Eci), stream_state(second(Indicator), Eci), fnc1(second, Indicator), [], PayloadBits, Rest) :- split_at(8, Bits0, PayloadBits, Rest), bits_int(PayloadBits, Indicator). parse_stream_item(_Version, structured_append, Bits0, State, State, structured_append(Index, Total, Parity), [], PayloadBits, Rest) :- split_at(4, Bits0, IndexBits, Bits1), split_at(4, Bits1, TotalBits, Bits2), split_at(8, Bits2, ParityBits, Rest), bits_int(IndexBits, Index), bits_int(TotalBits, Total), bits_int(ParityBits, Parity), append(IndexBits, TotalBits, Bits3), append(Bits3, ParityBits, PayloadBits). parse_eci_payload_bits(Bits0, Assignment, PayloadBits, Rest) :- split_at(8, Bits0, FirstBits, Bits1), bits_int(FirstBits, FirstByte), ( FirstByte < 128 -> Assignment = FirstByte, PayloadBits = FirstBits, Rest = Bits1 ; FirstByte < 192 -> split_at(8, Bits1, SecondBits, Rest), bits_int(SecondBits, SecondByte), Assignment is ((FirstByte /\ 63) << 8) \/ SecondByte, append(FirstBits, SecondBits, PayloadBits) ; FirstByte < 224 -> split_at(16, Bits1, TailBits, Rest), bits_int(TailBits, TailValue), Assignment is ((FirstByte /\ 31) << 16) \/ TailValue, append(FirstBits, TailBits, PayloadBits) ). fnc1_alphanumeric_encode(none, Codes, Codes) :- alphanumeric_codes(Codes). fnc1_alphanumeric_encode(Fnc1, Codes, EncodedCodes) :- fnc1_active(Fnc1), fnc1_alphanumeric_encode_codes(Codes, EncodedCodes). fnc1_alphanumeric_encode_codes([], []). fnc1_alphanumeric_encode_codes([29|Codes], [0'%|EncodedCodes]) :- !, fnc1_alphanumeric_encode_codes(Codes, EncodedCodes). fnc1_alphanumeric_encode_codes([0'%|Codes], [0'%,0'%|EncodedCodes]) :- !, fnc1_alphanumeric_encode_codes(Codes, EncodedCodes). fnc1_alphanumeric_encode_codes([Code|Codes], [Code|EncodedCodes]) :- alphanumeric_value(Code, _Value), fnc1_alphanumeric_encode_codes(Codes, EncodedCodes). fnc1_alphanumeric_decode(none, Codes, Codes). fnc1_alphanumeric_decode(Fnc1, EncodedCodes, Codes) :- fnc1_active(Fnc1), fnc1_alphanumeric_decode_codes(EncodedCodes, Codes). fnc1_active(first). fnc1_active(second(_Indicator)). fnc1_alphanumeric_decode_codes([], []). fnc1_alphanumeric_decode_codes([0'%,0'%|Codes], [0'%|DecodedCodes]) :- !, fnc1_alphanumeric_decode_codes(Codes, DecodedCodes). fnc1_alphanumeric_decode_codes([0'%|Codes], [29|DecodedCodes]) :- !, fnc1_alphanumeric_decode_codes(Codes, DecodedCodes). fnc1_alphanumeric_decode_codes([Code|Codes], [Code|DecodedCodes]) :- fnc1_alphanumeric_decode_codes(Codes, DecodedCodes). decode_stream_data(Items, Data) :- ( simple_stream_codes(Items, Codes), codes_text(Codes, Data) ; denormalize_qr_items(Items, ExternalItems), Data = qr_data(ExternalItems) ). simple_stream_codes(Items, Codes) :- simple_stream_codes(Items, latin1, Codes). simple_stream_codes([], _Encoding, []). simple_stream_codes([eci(Assignment)|Items], _OldEncoding, Codes) :- eci_text_encoding(Assignment, Encoding), simple_stream_codes(Items, Encoding, Codes). simple_stream_codes([Item|Items], Encoding, Codes) :- simple_text_segment_codes(Item, SegmentCodes), simple_stream_codes(Items, Encoding, RestCodes), append(SegmentCodes, RestCodes, Codes). simple_stream_codes([byte(Bytes)|Items], Encoding, Codes) :- encoding_bytes_codes(Encoding, Bytes, SegmentCodes), simple_stream_codes(Items, Encoding, RestCodes), append(SegmentCodes, RestCodes, Codes). simple_text_segment_codes(numeric(Codes), Codes). simple_text_segment_codes(alphanumeric(Codes), Codes). simple_text_segment_codes(kanji(Codes), Codes). eci_text_encoding(3, latin1). eci_text_encoding(25, utf16be). eci_text_encoding(26, utf8). eci_text_encoding(27, ascii). denormalize_qr_items([], []). denormalize_qr_items([eci(Assignment), byte(Bytes)|Items], [ExternalItem|ExternalItems]) :- denormalize_eci_text_item(Assignment, Bytes, ExternalItem), !, denormalize_qr_items(Items, ExternalItems). denormalize_qr_items([Item|Items], [ExternalItem|ExternalItems]) :- denormalize_qr_item(Item, ExternalItem), denormalize_qr_items(Items, ExternalItems). denormalize_eci_text_item(Assignment, Bytes, ExternalItem) :- eci_text_encoding(Assignment, Encoding), encoding_bytes_codes(Encoding, Bytes, Codes), codes_text(Codes, Text), external_eci_text_item(Encoding, Assignment, Text, ExternalItem). external_eci_text_item(latin1, _Assignment, Text, latin1(Text)). external_eci_text_item(ascii, _Assignment, Text, ascii(Text)). external_eci_text_item(utf8, _Assignment, Text, utf8(Text)). external_eci_text_item(utf16be, _Assignment, Text, utf16be(Text)). denormalize_qr_item(numeric(Codes), numeric(Text)) :- codes_text(Codes, Text). denormalize_qr_item(alphanumeric(Codes), alphanumeric(Text)) :- codes_text(Codes, Text). denormalize_qr_item(kanji(Codes), kanji(Text)) :- codes_text(Codes, Text). denormalize_qr_item(byte(Bytes), byte(Bytes)). denormalize_qr_item(eci(Assignment), eci(Assignment)). denormalize_qr_item(fnc1(first), fnc1(first)). denormalize_qr_item(fnc1(second, Indicator), fnc1(second, Indicator)). denormalize_qr_item(structured_append(Index, Total, Parity), structured_append(Index, Total, Parity)). utf8_bytes_from_codes([], []). utf8_bytes_from_codes([Code|Codes], Bytes) :- unicode_scalar_value(Code), utf8_code_bytes(Code, HeadBytes), utf8_bytes_from_codes(Codes, TailBytes), append(HeadBytes, TailBytes, Bytes). utf8_bytes_codes(Bytes, Codes) :- utf8_bytes_codes(Bytes, Codes, []). utf8_bytes_codes([], Codes, Codes). utf8_bytes_codes([Byte|Bytes], [Code|Codes0], Codes) :- utf8_lead_length(Byte, Width), split_at(Width, [Byte|Bytes], Sequence, RestBytes), utf8_sequence_code(Sequence, Code), utf8_bytes_codes(RestBytes, Codes0, Codes). utf16be_bytes_from_codes([], []). utf16be_bytes_from_codes([Code|Codes], Bytes) :- utf16be_code_words(Code, Words), utf16be_words_bytes(Words, HeadBytes), utf16be_bytes_from_codes(Codes, TailBytes), append(HeadBytes, TailBytes, Bytes). utf16be_code_words(Code, [Code]) :- unicode_scalar_value(Code), Code < 65536, !. utf16be_code_words(Code, [High, Low]) :- unicode_scalar_value(Code), Code1 is Code - 65536, High is 55296 + (Code1 >> 10), Low is 56320 + (Code1 /\ 1023). utf16be_words_bytes([], []). utf16be_words_bytes([Word|Words], [HighByte, LowByte|Bytes]) :- HighByte is (Word >> 8) /\ 255, LowByte is Word /\ 255, utf16be_words_bytes(Words, Bytes). utf16be_bytes_codes(Bytes, Codes) :- utf16be_words(Bytes, Words), utf16be_words_codes(Words, Codes). utf16be_words([], []). utf16be_words([HighByte, LowByte|Bytes], [Word|Words]) :- Word is (HighByte << 8) \/ LowByte, utf16be_words(Bytes, Words). utf16be_words_codes([], []). utf16be_words_codes([Word|Words], [Code|Codes]) :- utf16be_word_code(Word, Words, RestWords, Code), utf16be_words_codes(RestWords, Codes). utf16be_word_code(Word, Words, Words, Word) :- utf16be_scalar_word(Word). utf16be_word_code(High, [Low|Words], Words, Code) :- utf16be_high_surrogate(High), utf16be_low_surrogate(Low), Code is 65536 + ((High - 55296) << 10) + (Low - 56320). utf16be_scalar_word(Word) :- integer(Word), Word >= 0, Word =< 65535, (Word < 55296 ; Word > 57343). utf16be_high_surrogate(Word) :- integer(Word), Word >= 55296, Word =< 56319. utf16be_low_surrogate(Word) :- integer(Word), Word >= 56320, Word =< 57343. unicode_scalar_value(Code) :- integer(Code), Code >= 0, Code =< 1114111, (Code < 55296 ; Code > 57343). utf8_code_bytes(Code, [Code]) :- Code < 128, !. utf8_code_bytes(Code, [Byte1, Byte2]) :- Code < 2048, !, Byte1 is 192 \/ (Code >> 6), Byte2 is 128 \/ (Code /\ 63). utf8_code_bytes(Code, [Byte1, Byte2, Byte3]) :- Code < 65536, !, Byte1 is 224 \/ (Code >> 12), Byte2 is 128 \/ ((Code >> 6) /\ 63), Byte3 is 128 \/ (Code /\ 63). utf8_code_bytes(Code, [Byte1, Byte2, Byte3, Byte4]) :- Byte1 is 240 \/ (Code >> 18), Byte2 is 128 \/ ((Code >> 12) /\ 63), Byte3 is 128 \/ ((Code >> 6) /\ 63), Byte4 is 128 \/ (Code /\ 63). utf8_lead_length(Byte, 1) :- Byte < 128, !. utf8_lead_length(Byte, 2) :- Byte >= 194, Byte =< 223, !. utf8_lead_length(Byte, 3) :- Byte >= 224, Byte =< 239, !. utf8_lead_length(Byte, 4) :- Byte >= 240, Byte =< 244. utf8_sequence_code([Byte], Byte) :- Byte < 128. utf8_sequence_code([Byte1, Byte2], Code) :- continuation_byte(Byte2), Code is ((Byte1 /\ 31) << 6) \/ (Byte2 /\ 63), Code >= 128. utf8_sequence_code([Byte1, Byte2, Byte3], Code) :- continuation_byte(Byte2), continuation_byte(Byte3), Code is ((Byte1 /\ 15) << 12) \/ ((Byte2 /\ 63) << 6) \/ (Byte3 /\ 63), Code >= 2048, unicode_scalar_value(Code). utf8_sequence_code([Byte1, Byte2, Byte3, Byte4], Code) :- continuation_byte(Byte2), continuation_byte(Byte3), continuation_byte(Byte4), Code is ((Byte1 /\ 7) << 18) \/ ((Byte2 /\ 63) << 12) \/ ((Byte3 /\ 63) << 6) \/ (Byte4 /\ 63), Code >= 65536, unicode_scalar_value(Code). continuation_byte(Byte) :- Byte >= 128, Byte < 192. % Canonical Kanji mapping used in both directions: % Unicode code point <-> QR Kanji payload value kanji_qr(162, 81). kanji_qr(163, 82). kanji_qr(167, 88). kanji_qr(168, 14). kanji_qr(172, 138). kanji_qr(176, 75). kanji_qr(177, 61). kanji_qr(180, 12). kanji_qr(182, 183). kanji_qr(215, 62). kanji_qr(247, 64). kanji_qr(913, 479). kanji_qr(914, 480). kanji_qr(915, 481). kanji_qr(916, 482). kanji_qr(917, 483). kanji_qr(918, 484). kanji_qr(919, 485). kanji_qr(920, 486). kanji_qr(921, 487). kanji_qr(922, 488). kanji_qr(923, 489). kanji_qr(924, 490). kanji_qr(925, 491). kanji_qr(926, 492). kanji_qr(927, 493). kanji_qr(928, 494). kanji_qr(929, 495). kanji_qr(931, 496). kanji_qr(932, 497). kanji_qr(933, 498). kanji_qr(934, 499). kanji_qr(935, 500). kanji_qr(936, 501). kanji_qr(937, 502). kanji_qr(945, 511). kanji_qr(946, 512). kanji_qr(947, 513). kanji_qr(948, 514). kanji_qr(949, 515). kanji_qr(950, 516). kanji_qr(951, 517). kanji_qr(952, 518). kanji_qr(953, 519). kanji_qr(954, 520). kanji_qr(955, 521). kanji_qr(956, 522). kanji_qr(957, 523). kanji_qr(958, 524). kanji_qr(959, 525). kanji_qr(960, 526). kanji_qr(961, 527). kanji_qr(963, 528). kanji_qr(964, 529). kanji_qr(965, 530). kanji_qr(966, 531). kanji_qr(967, 532). kanji_qr(968, 533). kanji_qr(969, 534). kanji_qr(1025, 582). kanji_qr(1040, 576). kanji_qr(1041, 577). kanji_qr(1042, 578). kanji_qr(1043, 579). kanji_qr(1044, 580). kanji_qr(1045, 581). kanji_qr(1046, 583). kanji_qr(1047, 584). kanji_qr(1048, 585). kanji_qr(1049, 586). kanji_qr(1050, 587). kanji_qr(1051, 588). kanji_qr(1052, 589). kanji_qr(1053, 590). kanji_qr(1054, 591). kanji_qr(1055, 592). kanji_qr(1056, 593). kanji_qr(1057, 594). kanji_qr(1058, 595). kanji_qr(1059, 596). kanji_qr(1060, 597). kanji_qr(1061, 598). kanji_qr(1062, 599). kanji_qr(1063, 600). kanji_qr(1064, 601). kanji_qr(1065, 602). kanji_qr(1066, 603). kanji_qr(1067, 604). kanji_qr(1068, 605). kanji_qr(1069, 606). kanji_qr(1070, 607). kanji_qr(1071, 608). kanji_qr(1072, 624). kanji_qr(1073, 625). kanji_qr(1074, 626). kanji_qr(1075, 627). kanji_qr(1076, 628). kanji_qr(1077, 629). kanji_qr(1078, 631). kanji_qr(1079, 632). kanji_qr(1080, 633). kanji_qr(1081, 634). kanji_qr(1082, 635). kanji_qr(1083, 636). kanji_qr(1084, 637). kanji_qr(1085, 638). kanji_qr(1086, 640). kanji_qr(1087, 641). kanji_qr(1088, 642). kanji_qr(1089, 643). kanji_qr(1090, 644). kanji_qr(1091, 645). kanji_qr(1092, 646). kanji_qr(1093, 647). kanji_qr(1094, 648). kanji_qr(1095, 649). kanji_qr(1096, 650). kanji_qr(1097, 651). kanji_qr(1098, 652). kanji_qr(1099, 653). kanji_qr(1100, 654). kanji_qr(1101, 655). kanji_qr(1102, 656). kanji_qr(1103, 657). kanji_qr(1105, 630). kanji_qr(8208, 29). kanji_qr(8213, 28). kanji_qr(8214, 33). kanji_qr(8216, 37). kanji_qr(8217, 38). kanji_qr(8220, 39). kanji_qr(8221, 40). kanji_qr(8224, 181). kanji_qr(8225, 182). kanji_qr(8229, 36). kanji_qr(8230, 35). kanji_qr(8240, 177). kanji_qr(8242, 76). kanji_qr(8243, 77). kanji_qr(8251, 102). kanji_qr(8451, 78). kanji_qr(8491, 176). kanji_qr(8592, 105). kanji_qr(8593, 106). kanji_qr(8594, 104). kanji_qr(8595, 107). kanji_qr(8658, 139). kanji_qr(8660, 140). kanji_qr(8704, 141). kanji_qr(8706, 157). kanji_qr(8707, 142). kanji_qr(8711, 158). kanji_qr(8712, 120). kanji_qr(8715, 121). kanji_qr(8722, 60). kanji_qr(8730, 163). kanji_qr(8733, 165). kanji_qr(8734, 71). kanji_qr(8736, 154). kanji_qr(8743, 136). kanji_qr(8744, 137). kanji_qr(8745, 127). kanji_qr(8746, 126). kanji_qr(8747, 167). kanji_qr(8748, 168). kanji_qr(8756, 72). kanji_qr(8757, 166). kanji_qr(8765, 164). kanji_qr(8786, 160). kanji_qr(8800, 66). kanji_qr(8801, 159). kanji_qr(8806, 69). kanji_qr(8807, 70). kanji_qr(8810, 161). kanji_qr(8811, 162). kanji_qr(8834, 124). kanji_qr(8835, 125). kanji_qr(8838, 122). kanji_qr(8839, 123). kanji_qr(8869, 155). kanji_qr(8978, 156). kanji_qr(9472, 671). kanji_qr(9473, 682). kanji_qr(9474, 672). kanji_qr(9475, 683). kanji_qr(9484, 673). kanji_qr(9487, 684). kanji_qr(9488, 674). kanji_qr(9491, 685). kanji_qr(9492, 676). kanji_qr(9495, 687). kanji_qr(9496, 675). kanji_qr(9499, 686). kanji_qr(9500, 677). kanji_qr(9501, 698). kanji_qr(9504, 693). kanji_qr(9507, 688). kanji_qr(9508, 679). kanji_qr(9509, 700). kanji_qr(9512, 695). kanji_qr(9515, 690). kanji_qr(9516, 678). kanji_qr(9519, 694). kanji_qr(9520, 699). kanji_qr(9523, 689). kanji_qr(9524, 680). kanji_qr(9527, 696). kanji_qr(9528, 701). kanji_qr(9531, 691). kanji_qr(9532, 681). kanji_qr(9535, 697). kanji_qr(9538, 702). kanji_qr(9547, 692). kanji_qr(9632, 97). kanji_qr(9633, 96). kanji_qr(9650, 99). kanji_qr(9651, 98). kanji_qr(9660, 101). kanji_qr(9661, 100). kanji_qr(9670, 95). kanji_qr(9671, 94). kanji_qr(9675, 91). kanji_qr(9678, 93). kanji_qr(9679, 92). kanji_qr(9711, 188). kanji_qr(9733, 90). kanji_qr(9734, 89). kanji_qr(9792, 74). kanji_qr(9794, 73). kanji_qr(9834, 180). kanji_qr(9837, 179). kanji_qr(9839, 178). kanji_qr(12288, 0). kanji_qr(12289, 1). kanji_qr(12290, 2). kanji_qr(12291, 22). kanji_qr(12293, 24). kanji_qr(12294, 25). kanji_qr(12295, 26). kanji_qr(12296, 49). kanji_qr(12297, 50). kanji_qr(12298, 51). kanji_qr(12299, 52). kanji_qr(12300, 53). kanji_qr(12301, 54). kanji_qr(12302, 55). kanji_qr(12303, 56). kanji_qr(12304, 57). kanji_qr(12305, 58). kanji_qr(12306, 103). kanji_qr(12307, 108). kanji_qr(12308, 43). kanji_qr(12309, 44). kanji_qr(12316, 32). kanji_qr(12353, 287). kanji_qr(12354, 288). kanji_qr(12355, 289). kanji_qr(12356, 290). kanji_qr(12357, 291). kanji_qr(12358, 292). kanji_qr(12359, 293). kanji_qr(12360, 294). kanji_qr(12361, 295). kanji_qr(12362, 296). kanji_qr(12363, 297). kanji_qr(12364, 298). kanji_qr(12365, 299). kanji_qr(12366, 300). kanji_qr(12367, 301). kanji_qr(12368, 302). kanji_qr(12369, 303). kanji_qr(12370, 304). kanji_qr(12371, 305). kanji_qr(12372, 306). kanji_qr(12373, 307). kanji_qr(12374, 308). kanji_qr(12375, 309). kanji_qr(12376, 310). kanji_qr(12377, 311). kanji_qr(12378, 312). kanji_qr(12379, 313). kanji_qr(12380, 314). kanji_qr(12381, 315). kanji_qr(12382, 316). kanji_qr(12383, 317). kanji_qr(12384, 318). kanji_qr(12385, 319). kanji_qr(12386, 320). kanji_qr(12387, 321). kanji_qr(12388, 322). kanji_qr(12389, 323). kanji_qr(12390, 324). kanji_qr(12391, 325). kanji_qr(12392, 326). kanji_qr(12393, 327). kanji_qr(12394, 328). kanji_qr(12395, 329). kanji_qr(12396, 330). kanji_qr(12397, 331). kanji_qr(12398, 332). kanji_qr(12399, 333). kanji_qr(12400, 334). kanji_qr(12401, 335). kanji_qr(12402, 336). kanji_qr(12403, 337). kanji_qr(12404, 338). kanji_qr(12405, 339). kanji_qr(12406, 340). kanji_qr(12407, 341). kanji_qr(12408, 342). kanji_qr(12409, 343). kanji_qr(12410, 344). kanji_qr(12411, 345). kanji_qr(12412, 346). kanji_qr(12413, 347). kanji_qr(12414, 348). kanji_qr(12415, 349). kanji_qr(12416, 350). kanji_qr(12417, 351). kanji_qr(12418, 352). kanji_qr(12419, 353). kanji_qr(12420, 354). kanji_qr(12421, 355). kanji_qr(12422, 356). kanji_qr(12423, 357). kanji_qr(12424, 358). kanji_qr(12425, 359). kanji_qr(12426, 360). kanji_qr(12427, 361). kanji_qr(12428, 362). kanji_qr(12429, 363). kanji_qr(12430, 364). kanji_qr(12431, 365). kanji_qr(12432, 366). kanji_qr(12433, 367). kanji_qr(12434, 368). kanji_qr(12435, 369). kanji_qr(12443, 10). kanji_qr(12444, 11). kanji_qr(12445, 20). kanji_qr(12446, 21). kanji_qr(12449, 384). kanji_qr(12450, 385). kanji_qr(12451, 386). kanji_qr(12452, 387). kanji_qr(12453, 388). kanji_qr(12454, 389). kanji_qr(12455, 390). kanji_qr(12456, 391). kanji_qr(12457, 392). kanji_qr(12458, 393). kanji_qr(12459, 394). kanji_qr(12460, 395). kanji_qr(12461, 396). kanji_qr(12462, 397). kanji_qr(12463, 398). kanji_qr(12464, 399). kanji_qr(12465, 400). kanji_qr(12466, 401). kanji_qr(12467, 402). kanji_qr(12468, 403). kanji_qr(12469, 404). kanji_qr(12470, 405). kanji_qr(12471, 406). kanji_qr(12472, 407). kanji_qr(12473, 408). kanji_qr(12474, 409). kanji_qr(12475, 410). kanji_qr(12476, 411). kanji_qr(12477, 412). kanji_qr(12478, 413). kanji_qr(12479, 414). kanji_qr(12480, 415). kanji_qr(12481, 416). kanji_qr(12482, 417). kanji_qr(12483, 418). kanji_qr(12484, 419). kanji_qr(12485, 420). kanji_qr(12486, 421). kanji_qr(12487, 422). kanji_qr(12488, 423). kanji_qr(12489, 424). kanji_qr(12490, 425). kanji_qr(12491, 426). kanji_qr(12492, 427). kanji_qr(12493, 428). kanji_qr(12494, 429). kanji_qr(12495, 430). kanji_qr(12496, 431). kanji_qr(12497, 432). kanji_qr(12498, 433). kanji_qr(12499, 434). kanji_qr(12500, 435). kanji_qr(12501, 436). kanji_qr(12502, 437). kanji_qr(12503, 438). kanji_qr(12504, 439). kanji_qr(12505, 440). kanji_qr(12506, 441). kanji_qr(12507, 442). kanji_qr(12508, 443). kanji_qr(12509, 444). kanji_qr(12510, 445). kanji_qr(12511, 446). kanji_qr(12512, 448). kanji_qr(12513, 449). kanji_qr(12514, 450). kanji_qr(12515, 451). kanji_qr(12516, 452). kanji_qr(12517, 453). kanji_qr(12518, 454). kanji_qr(12519, 455). kanji_qr(12520, 456). kanji_qr(12521, 457). kanji_qr(12522, 458). kanji_qr(12523, 459). kanji_qr(12524, 460). kanji_qr(12525, 461). kanji_qr(12526, 462). kanji_qr(12527, 463). kanji_qr(12528, 464). kanji_qr(12529, 465). kanji_qr(12530, 466). kanji_qr(12531, 467). kanji_qr(12532, 468). kanji_qr(12533, 469). kanji_qr(12534, 470). kanji_qr(12539, 5). kanji_qr(12540, 27). kanji_qr(12541, 18). kanji_qr(12542, 19). kanji_qr(19968, 1514). kanji_qr(19969, 3354). kanji_qr(19971, 2613). kanji_qr(19975, 4124). kanji_qr(19976, 2852). kanji_qr(19977, 2511). kanji_qr(19978, 2851). kanji_qr(19979, 1658). kanji_qr(19981, 3891). kanji_qr(19982, 4254). kanji_qr(19984, 4512). kanji_qr(19985, 1550). kanji_qr(19988, 1806). kanji_qr(19989, 4513). kanji_qr(19990, 2978). kanji_qr(19991, 4736). kanji_qr(19992, 1973). kanji_qr(19993, 3960). kanji_qr(19998, 2853). kanji_qr(20001, 4348). kanji_qr(20006, 3968). kanji_qr(20010, 4514). kanji_qr(20013, 3334). kanji_qr(20017, 4515). kanji_qr(20018, 2104). kanji_qr(20022, 4516). kanji_qr(20024, 1883). kanji_qr(20025, 3279). kanji_qr(20027, 2661). kanji_qr(20028, 4517). kanji_qr(20031, 4518). kanji_qr(20034, 4519). kanji_qr(20035, 3668). kanji_qr(20037, 1974). kanji_qr(20043, 3670). kanji_qr(20045, 3617). kanji_qr(20046, 2241). kanji_qr(20047, 4050). kanji_qr(20053, 6952). kanji_qr(20054, 4520). kanji_qr(20055, 2854). kanji_qr(20056, 4521). kanji_qr(20057, 1651). kanji_qr(20061, 2083). kanji_qr(20062, 2286). kanji_qr(20063, 4199). kanji_qr(20066, 5092). kanji_qr(20081, 4304). kanji_qr(20083, 3643). kanji_qr(20094, 1827). kanji_qr(20096, 1940). kanji_qr(20098, 4522). kanji_qr(20101, 4523). kanji_qr(20102, 4345). kanji_qr(20104, 4252). kanji_qr(20105, 3144). kanji_qr(20106, 4525). kanji_qr(20107, 2582). kanji_qr(20108, 3633). kanji_qr(20110, 4528). kanji_qr(20113, 1565). kanji_qr(20114, 2269). kanji_qr(20116, 2268). kanji_qr(20117, 1508). kanji_qr(20120, 4458). kanji_qr(20121, 4457). kanji_qr(20123, 2417). kanji_qr(20124, 1439). kanji_qr(20126, 4529). kanji_qr(20127, 4530). kanji_qr(20128, 4531). kanji_qr(20129, 4051). kanji_qr(20130, 4532). kanji_qr(20132, 2288). kanji_qr(20133, 1509). kanji_qr(20134, 4114). kanji_qr(20136, 2012). kanji_qr(20139, 2013). kanji_qr(20140, 2014). kanji_qr(20141, 3424). kanji_qr(20142, 4346). kanji_qr(20144, 4533). kanji_qr(20147, 4534). kanji_qr(20150, 4535). kanji_qr(20154, 2924). kanji_qr(20160, 2713). kanji_qr(20161, 2925). kanji_qr(20162, 4540). kanji_qr(20164, 4538). kanji_qr(20166, 4539). kanji_qr(20167, 1975). kanji_qr(20170, 2401). kanji_qr(20171, 1710). kanji_qr(20173, 4537). kanji_qr(20174, 4536). kanji_qr(20175, 3943). kanji_qr(20180, 2533). kanji_qr(20181, 2532). kanji_qr(20182, 3196). kanji_qr(20183, 4541). kanji_qr(20184, 3892). kanji_qr(20185, 3045). kanji_qr(20189, 23). kanji_qr(20190, 4542). kanji_qr(20191, 4544). kanji_qr(20195, 3235). kanji_qr(20196, 4383). kanji_qr(20197, 1480). kanji_qr(20205, 4543). kanji_qr(20206, 1660). kanji_qr(20208, 2050). kanji_qr(20210, 3335). kanji_qr(20214, 2191). kanji_qr(20215, 4545). kanji_qr(20219, 3651). kanji_qr(20225, 1897). kanji_qr(20233, 4546). kanji_qr(20234, 1481). kanji_qr(20237, 2270). kanji_qr(20238, 1898). kanji_qr(20239, 3930). kanji_qr(20240, 3760). kanji_qr(20241, 1976). kanji_qr(20250, 1711). kanji_qr(20252, 4581). kanji_qr(20253, 3488). kanji_qr(20271, 3724). kanji_qr(20272, 4548). kanji_qr(20276, 3770). kanji_qr(20278, 4384). kanji_qr(20280, 2892). kanji_qr(20282, 2534). kanji_qr(20284, 2583). kanji_qr(20285, 1662). kanji_qr(20291, 3407). kanji_qr(20294, 3265). kanji_qr(20295, 4552). kanji_qr(20301, 1482). kanji_qr(20302, 3425). kanji_qr(20303, 2714). kanji_qr(20304, 2418). kanji_qr(20305, 4227). kanji_qr(20307, 3212). kanji_qr(20309, 1661). kanji_qr(20311, 4551). kanji_qr(20313, 4253). kanji_qr(20314, 4547). kanji_qr(20315, 4549). kanji_qr(20316, 2476). kanji_qr(20317, 4550). kanji_qr(20318, 4995). kanji_qr(20329, 4558). kanji_qr(20335, 4561). kanji_qr(20336, 4559). kanji_qr(20339, 1664). kanji_qr(20341, 3961). kanji_qr(20342, 4553). kanji_qr(20347, 4557). kanji_qr(20348, 2289). kanji_qr(20351, 2535). kanji_qr(20355, 1828). kanji_qr(20358, 4562). kanji_qr(20360, 4554). kanji_qr(20363, 4385). kanji_qr(20365, 2584). kanji_qr(20367, 4555). kanji_qr(20369, 4560). kanji_qr(20374, 4563). kanji_qr(20376, 4556). kanji_qr(20379, 2015). kanji_qr(20381, 1483). kanji_qr(20384, 2016). kanji_qr(20385, 1663). kanji_qr(20395, 4996). kanji_qr(20397, 4121). kanji_qr(20398, 3918). kanji_qr(20399, 2290). kanji_qr(20405, 2894). kanji_qr(20406, 4341). kanji_qr(20415, 3990). kanji_qr(20418, 2135). kanji_qr(20419, 3171). kanji_qr(20420, 1698). kanji_qr(20426, 2738). kanji_qr(20430, 4567). kanji_qr(20432, 4572). kanji_qr(20433, 4570). kanji_qr(20436, 4565). kanji_qr(20439, 3181). kanji_qr(20440, 4568). kanji_qr(20442, 4571). kanji_qr(20443, 4569). kanji_qr(20445, 3995). kanji_qr(20447, 4566). kanji_qr(20449, 2893). kanji_qr(20451, 4115). kanji_qr(20452, 4573). kanji_qr(20453, 4574). kanji_qr(20462, 2691). kanji_qr(20463, 4587). kanji_qr(20467, 3695). kanji_qr(20469, 3861). kanji_qr(20470, 4582). kanji_qr(20472, 4014). kanji_qr(20474, 1652). kanji_qr(20478, 4586). kanji_qr(20485, 4580). kanji_qr(20486, 4589). kanji_qr(20489, 3121). kanji_qr(20491, 2242). kanji_qr(20493, 3707). kanji_qr(20495, 6085). kanji_qr(20497, 4588). kanji_qr(20498, 3516). kanji_qr(20500, 4577). kanji_qr(20502, 2292). kanji_qr(20505, 2291). kanji_qr(20506, 4575). kanji_qr(20511, 2648). kanji_qr(20513, 4583). kanji_qr(20515, 4013). kanji_qr(20516, 3308). kanji_qr(20517, 4579). kanji_qr(20518, 2193). kanji_qr(20520, 4576). kanji_qr(20521, 4584). kanji_qr(20522, 4578). kanji_qr(20523, 4367). kanji_qr(20524, 4585). kanji_qr(20525, 4448). kanji_qr(20534, 2084). kanji_qr(20537, 2192). kanji_qr(20547, 4590). kanji_qr(20551, 4591). kanji_qr(20552, 4595). kanji_qr(20553, 1484). kanji_qr(20559, 3982). kanji_qr(20560, 4594). kanji_qr(20565, 4593). kanji_qr(20566, 4597). kanji_qr(20570, 4596). kanji_qr(20572, 3426). kanji_qr(20581, 2194). kanji_qr(20588, 4598). kanji_qr(20594, 2627). kanji_qr(20596, 3172). kanji_qr(20597, 3427). kanji_qr(20598, 2100). kanji_qr(20600, 4599). kanji_qr(20605, 1941). kanji_qr(20608, 4600). kanji_qr(20613, 4602). kanji_qr(20621, 4052). kanji_qr(20625, 2182). kanji_qr(20632, 2512). kanji_qr(20633, 3829). kanji_qr(20634, 4601). kanji_qr(20652, 2435). kanji_qr(20653, 4258). kanji_qr(20658, 4604). kanji_qr(20659, 4610). kanji_qr(20660, 4603). kanji_qr(20661, 2434). kanji_qr(20663, 2781). kanji_qr(20670, 2136). kanji_qr(20674, 4611). kanji_qr(20677, 2061). kanji_qr(20681, 4608). kanji_qr(20682, 4609). kanji_qr(20685, 3565). kanji_qr(20687, 3164). kanji_qr(20689, 2017). kanji_qr(20693, 4076). kanji_qr(20694, 4612). kanji_qr(20698, 4347). kanji_qr(20702, 4613). kanji_qr(20707, 4616). kanji_qr(20709, 4614). kanji_qr(20711, 3117). kanji_qr(20717, 4615). kanji_qr(20718, 4617). kanji_qr(20725, 4619). kanji_qr(20729, 4618). kanji_qr(20731, 3974). kanji_qr(20736, 1942). kanji_qr(20737, 4621). kanji_qr(20738, 4622). kanji_qr(20740, 1645). kanji_qr(20745, 4620). kanji_qr(20754, 2674). kanji_qr(20756, 4625). kanji_qr(20757, 4624). kanji_qr(20758, 4623). kanji_qr(20760, 4564). kanji_qr(20762, 4626). kanji_qr(20767, 2782). kanji_qr(20769, 4627). kanji_qr(20778, 4228). kanji_qr(20786, 4183). kanji_qr(20791, 4629). kanji_qr(20794, 4628). kanji_qr(20795, 4631). kanji_qr(20796, 4630). kanji_qr(20799, 4632). kanji_qr(20800, 4633). kanji_qr(20801, 1522). kanji_qr(20803, 2227). kanji_qr(20804, 2138). kanji_qr(20805, 2715). kanji_qr(20806, 3355). kanji_qr(20807, 2018). kanji_qr(20808, 3046). kanji_qr(20809, 2293). kanji_qr(20811, 2382). kanji_qr(20812, 4635). kanji_qr(20813, 4166). kanji_qr(20814, 3493). kanji_qr(20816, 2585). kanji_qr(20818, 4634). kanji_qr(20820, 4636). kanji_qr(20826, 3517). kanji_qr(20828, 1813). kanji_qr(20834, 4637). kanji_qr(20837, 3644). kanji_qr(20840, 3091). kanji_qr(20841, 4639). kanji_qr(20842, 4640). kanji_qr(20843, 3754). kanji_qr(20844, 2294). kanji_qr(20845, 4442). kanji_qr(20846, 4641). kanji_qr(20849, 2020). kanji_qr(20853, 3962). kanji_qr(20854, 3188). kanji_qr(20855, 2095). kanji_qr(20856, 3476). kanji_qr(20860, 2195). kanji_qr(20864, 4642). kanji_qr(20866, 4643). kanji_qr(20869, 3616). kanji_qr(20870, 1598). kanji_qr(20873, 4646). kanji_qr(20874, 2491). kanji_qr(20876, 4645). kanji_qr(20877, 2436). kanji_qr(20879, 4647). kanji_qr(20880, 6700). kanji_qr(20881, 4648). kanji_qr(20882, 4064). kanji_qr(20883, 4649). kanji_qr(20885, 4650). kanji_qr(20886, 4651). kanji_qr(20887, 2855). kanji_qr(20889, 2634). kanji_qr(20896, 1829). kanji_qr(20898, 4654). kanji_qr(20900, 4652). kanji_qr(20901, 4155). kanji_qr(20902, 4653). kanji_qr(20904, 3897). kanji_qr(20905, 4655). kanji_qr(20906, 4656). kanji_qr(20907, 4657). kanji_qr(20908, 3518). kanji_qr(20912, 4661). kanji_qr(20913, 4659). kanji_qr(20914, 4660). kanji_qr(20915, 4658). kanji_qr(20916, 2465). kanji_qr(20917, 4662). kanji_qr(20918, 4200). kanji_qr(20919, 4386). kanji_qr(20925, 4663). kanji_qr(20932, 2982). kanji_qr(20933, 4664). kanji_qr(20934, 2745). kanji_qr(20937, 4665). kanji_qr(20939, 3356). kanji_qr(20940, 4349). kanji_qr(20941, 3520). kanji_qr(20950, 4739). kanji_qr(20955, 4666). kanji_qr(20956, 7971). kanji_qr(20957, 2051). kanji_qr(20960, 4667). kanji_qr(20961, 4093). kanji_qr(20966, 2760). kanji_qr(20967, 3258). kanji_qr(20969, 4669). kanji_qr(20970, 3618). kanji_qr(20973, 4670). kanji_qr(20976, 4672). kanji_qr(20977, 1741). kanji_qr(20981, 4673). kanji_qr(20982, 2021). kanji_qr(20984, 3594). kanji_qr(20985, 1626). kanji_qr(20986, 2735). kanji_qr(20989, 3743). kanji_qr(20990, 4674). kanji_qr(20992, 3521). kanji_qr(20995, 2926). kanji_qr(20996, 4675). kanji_qr(20998, 3946). kanji_qr(20999, 3032). kanji_qr(21000, 1824). kanji_qr(21002, 1831). kanji_qr(21003, 4676). kanji_qr(21006, 4678). kanji_qr(21009, 2137). kanji_qr(21012, 4677). kanji_qr(21015, 4401). kanji_qr(21021, 2761). kanji_qr(21028, 3771). kanji_qr(21029, 3978). kanji_qr(21031, 4679). kanji_qr(21033, 4312). kanji_qr(21034, 4680). kanji_qr(21038, 4681). kanji_qr(21040, 3550). kanji_qr(21043, 4682). kanji_qr(21046, 2983). kanji_qr(21047, 2492). kanji_qr(21048, 2196). kanji_qr(21049, 4683). kanji_qr(21050, 2536). kanji_qr(21051, 2383). kanji_qr(21059, 3428). kanji_qr(21060, 4685). kanji_qr(21063, 3173). kanji_qr(21066, 2477). kanji_qr(21067, 4686). kanji_qr(21068, 4687). kanji_qr(21069, 3087). kanji_qr(21071, 4684). kanji_qr(21076, 4689). kanji_qr(21078, 4053). kanji_qr(21083, 2372). kanji_qr(21086, 4688). kanji_qr(21091, 2197). kanji_qr(21092, 2460). kanji_qr(21093, 3725). kanji_qr(21097, 4692). kanji_qr(21098, 4690). kanji_qr(21103, 3931). kanji_qr(21104, 2856). kanji_qr(21105, 4699). kanji_qr(21106, 1796). kanji_qr(21107, 4693). kanji_qr(21108, 4691). kanji_qr(21109, 3118). kanji_qr(21117, 4695). kanji_qr(21119, 4694). kanji_qr(21123, 1763). kanji_qr(21127, 2176). kanji_qr(21128, 4700). kanji_qr(21129, 4331). kanji_qr(21133, 4696). kanji_qr(21137, 4701). kanji_qr(21138, 4698). kanji_qr(21140, 4697). kanji_qr(21147, 4365). kanji_qr(21151, 2295). kanji_qr(21152, 1665). kanji_qr(21155, 4402). kanji_qr(21161, 2773). kanji_qr(21162, 3511). kanji_qr(21163, 2373). kanji_qr(21164, 4704). kanji_qr(21165, 4705). kanji_qr(21169, 4387). kanji_qr(21172, 4426). kanji_qr(21173, 4707). kanji_qr(21177, 2296). kanji_qr(21180, 4706). kanji_qr(21182, 1742). kanji_qr(21185, 4708). kanji_qr(21187, 4085). kanji_qr(21189, 3386). kanji_qr(21191, 4229). kanji_qr(21193, 3991). kanji_qr(21197, 4709). kanji_qr(21202, 7635). kanji_qr(21205, 3566). kanji_qr(21207, 4710). kanji_qr(21208, 1832). kanji_qr(21209, 4145). kanji_qr(21213, 2783). kanji_qr(21214, 4711). kanji_qr(21215, 4005). kanji_qr(21216, 4715). kanji_qr(21218, 2984). kanji_qr(21219, 4712). kanji_qr(21220, 2062). kanji_qr(21222, 4713). kanji_qr(21223, 1833). kanji_qr(21234, 2125). kanji_qr(21235, 4716). kanji_qr(21237, 4717). kanji_qr(21240, 4718). kanji_qr(21241, 4719). kanji_qr(21242, 2649). kanji_qr(21246, 2297). kanji_qr(21247, 4188). kanji_qr(21249, 4198). kanji_qr(21250, 3637). kanji_qr(21253, 4015). kanji_qr(21254, 4720). kanji_qr(21256, 4721). kanji_qr(21261, 4723). kanji_qr(21263, 4725). kanji_qr(21264, 4724). kanji_qr(21269, 4726). kanji_qr(21270, 1659). kanji_qr(21271, 4075). kanji_qr(21273, 2490). kanji_qr(21274, 4727). kanji_qr(21277, 3128). kanji_qr(21280, 2784). kanji_qr(21281, 2023). kanji_qr(21283, 4728). kanji_qr(21290, 3801). kanji_qr(21295, 4729). kanji_qr(21297, 4730). kanji_qr(21299, 4731). kanji_qr(21304, 4732). kanji_qr(21305, 3843). %% Reed-Solomon block layout and interleaving % % QR codes do not apply one giant RS code over the whole payload. Each version % and EC level defines one or more blocks, each block gets its own parity % words, and only then are the block columns interleaved. rs_blocks(Version, Level, Blocks) :- rs_block_groups(Version, Level, Groups), expand_block_groups(Groups, Blocks). expand_block_groups([], []). expand_block_groups([block_group(Count, TotalCount, DataCount)|Groups], Blocks) :- EccCount is TotalCount - DataCount, repeat_block(Count, block(DataCount, EccCount), GroupBlocks), expand_block_groups(Groups, RestBlocks), append(GroupBlocks, RestBlocks, Blocks). repeat_block(0, _Block, []). repeat_block(Count, Block, [Block|Blocks]) :- Count > 0, Count1 is Count - 1, repeat_block(Count1, Block, Blocks). total_data_word_count(Version, Level, Count) :- rs_blocks(Version, Level, Blocks), maplist(block_data_count, Blocks, Counts), sum_lengths(Counts, Count). total_codeword_count(Version, Level, Count) :- rs_blocks(Version, Level, Blocks), maplist(block_total_count, Blocks, Counts), sum_lengths(Counts, Count). block_data_count(block(DataCount, _EccCount), DataCount). block_ecc_count(block(_DataCount, EccCount), EccCount). block_total_count(block(DataCount, EccCount), TotalCount) :- TotalCount is DataCount + EccCount. blocks_data_words(Words, Blocks, DataBlocks) :- blocks_data_words(Words, Blocks, DataBlocks, []). blocks_data_words(Rest, [], [], Rest). blocks_data_words(Words0, [block(DataCount, _EccCount)|Blocks], [DataBlock|DataBlocks], RestWords) :- split_at(DataCount, Words0, DataBlock, Words1), blocks_data_words(Words1, Blocks, DataBlocks, RestWords). blocks_ecc_words([], [], []). blocks_ecc_words([DataBlock|DataBlocks], [block(_DataCount, EccCount)|Blocks], [EccBlock|EccBlocks]) :- rs_ecc(DataBlock, EccCount, EccBlock), blocks_ecc_words(DataBlocks, Blocks, EccBlocks). % correct_ecc_blocks/6 is the bridge between the QR block layout and the % symbol-level RS repair logic below. correct_ecc_blocks([], [], [], [], [], []). correct_ecc_blocks([ReceivedDataBlock|ReceivedDataBlocks], [ReceivedEccBlock|ReceivedEccBlocks], [block(DataCount, EccCount)|Blocks], [DataBlock|DataBlocks], [EccBlock|EccBlocks], [Correction|Corrections]) :- append(ReceivedDataBlock, ReceivedEccBlock, ReceivedBlock), rs_correct_block(ReceivedBlock, EccCount, CorrectedBlock, Correction), split_at(DataCount, CorrectedBlock, DataBlock, EccBlock), correct_ecc_blocks(ReceivedDataBlocks, ReceivedEccBlocks, Blocks, DataBlocks, EccBlocks, Corrections). % QR interleaves columns: all first data words, then all second data words, % and only after that the parity columns. interleave_codewords(DataBlocks, EccBlocks, Codewords) :- interleave_blocks(DataBlocks, InterleavedData), interleave_blocks(EccBlocks, InterleavedEcc), append(InterleavedData, InterleavedEcc, Codewords). interleave_blocks(Blocks, Words) :- max_block_length(Blocks, MaxLength), interleave_columns(0, MaxLength, Blocks, Words). max_block_length([], 0). max_block_length([Block|Blocks], MaxLength) :- length(Block, BlockLength), max_block_length(Blocks, RestMaxLength), max_int(BlockLength, RestMaxLength, MaxLength). interleave_columns(Index, MaxLength, _Blocks, []) :- Index >= MaxLength, !. interleave_columns(Index, MaxLength, Blocks, Words) :- block_column(Blocks, Index, ColumnWords), Index1 is Index + 1, interleave_columns(Index1, MaxLength, Blocks, RestWords), append(ColumnWords, RestWords, Words). block_column([], _Index, []). block_column([Block|Blocks], Index, ColumnWords) :- ( nth0(Index, Block, Word) -> ColumnWords = [Word|RestWords] ; ColumnWords = RestWords ), block_column(Blocks, Index, RestWords). % Decode reverses the same column interleave separately for the data and ECC % regions of the received codeword stream. deinterleave_codewords(Blocks, Codewords, DataBlocks, EccBlocks) :- maplist(block_data_count, Blocks, DataLengths), sum_lengths(DataLengths, DataWordCount), split_at(DataWordCount, Codewords, DataWordsInterleaved, EccWordsInterleaved), deinterleave_segment(DataLengths, DataWordsInterleaved, DataBlocks), maplist(block_ecc_count, Blocks, EccLengths), deinterleave_segment(EccLengths, EccWordsInterleaved, EccBlocks). sum_lengths([], 0). sum_lengths([Length|Lengths], Sum) :- sum_lengths(Lengths, Rest), Sum is Length + Rest. deinterleave_segment(Lengths, Words, Blocks) :- empty_blocks(Lengths, EmptyBlocks), max_length_from_lengths(Lengths, MaxLength), deinterleave_columns(0, MaxLength, Lengths, Words, EmptyBlocks, ReversedBlocks), reverse_each(ReversedBlocks, Blocks). empty_blocks([], []). empty_blocks([_Length|Lengths], [[]|Blocks]) :- empty_blocks(Lengths, Blocks). max_length_from_lengths([], 0). max_length_from_lengths([Length|Lengths], MaxLength) :- max_length_from_lengths(Lengths, RestMaxLength), max_int(Length, RestMaxLength, MaxLength). deinterleave_columns(Index, MaxLength, _Lengths, Words, Blocks, Blocks) :- Index >= MaxLength, Words = [], !. deinterleave_columns(Index, MaxLength, Lengths, Words0, Blocks0, Blocks) :- deinterleave_column(Index, Lengths, Words0, Words1, Blocks0, Blocks1), Index1 is Index + 1, deinterleave_columns(Index1, MaxLength, Lengths, Words1, Blocks1, Blocks). deinterleave_column(_Index, [], Words, Words, [], []). deinterleave_column(Index, [Length|Lengths], Words0, Words, [Block0|Blocks0], [Block1|Blocks1]) :- ( Index < Length -> Words0 = [Word|WordsA], Block1 = [Word|Block0] ; WordsA = Words0, Block1 = Block0 ), deinterleave_column(Index, Lengths, WordsA, Words, Blocks0, Blocks1). reverse_each([], []). reverse_each([List|Lists], [Reversed|ReversedLists]) :- reverse(List, Reversed), reverse_each(Lists, ReversedLists). append_blocks([], []). append_blocks([Block|Blocks], Words) :- append_blocks(Blocks, RestWords), append(Block, RestWords, Words). fill_data_modules(CodewordBits, Positions, PlacementBits) :- length(Positions, PositionCount), length(CodewordBits, BitCount), BitCount =< PositionCount, PaddingCount is PositionCount - BitCount, zeros(PaddingCount, PaddingBits), append(CodewordBits, PaddingBits, PlacementBits). % Shared zero-list check used for terminator padding, syndromes, and other % places where a QR rule says "the remaining values must all be zero". all_zero([]). all_zero([0|Values]) :- all_zero(Values). %% Reed-Solomon over GF(256) % % Polynomials here use the usual QR byte field GF(2^8) with primitive % polynomial x^8 + x^4 + x^3 + x^2 + 1 (decimal 285). % % The code keeps coefficient lists in two different orders depending on the % task: % - codeword polynomials are evaluated in descending coefficient order % - locator and helper polynomials use ascending order [c0, c1, ...] % % rs_correct_block/4 now handles: % - no damage % - unknown hard errors % - known erasures % - mixed unknown errors + known erasures, with the QR bound 2e + s <= nsym rs_ecc(DataWords, EccCount, EccWords) :- generator_poly(EccCount, [_Leading|GeneratorTail]), zeros(EccCount, ZeroPadding), append(DataWords, ZeroPadding, Working), length(DataWords, DataCount), rs_reduce(DataCount, GeneratorTail, Working, EccWords). rs_reduce(0, _GeneratorTail, Remainder, Remainder). rs_reduce(Count, GeneratorTail, [Coefficient|Rest], Remainder) :- Count > 0, ( Coefficient =:= 0 -> Rest1 = Rest ; xor_scaled_prefix(Rest, GeneratorTail, Coefficient, Rest1) ), Count1 is Count - 1, rs_reduce(Count1, GeneratorTail, Rest1, Remainder). rs_correct_block(ReceivedCodewords, EccCount, CorrectedCodewords, Status) :- received_block_erasures(ReceivedCodewords, Codewords, ErasurePositions), qr_codeword_sequence(Codewords), length(ErasurePositions, ErasureCount), ErasureCount =< EccCount, rs_syndromes(Codewords, EccCount, Syndromes), rs_general_corrections(Codewords, Syndromes, EccCount, ErasurePositions, CorrectedCodewords, Corrections), correction_status(Corrections, Status), !. % The generalized decoder first derives an erasure locator from known missing % symbols, then searches over the remaining unknown-error count, derives a full % locator polynomial, solves magnitudes, and finally verifies that the repaired % block has zero syndromes. rs_general_corrections(Codewords, Syndromes, EccCount, ErasurePositions, CorrectedCodewords, Corrections) :- length(Codewords, CodewordCount), erasure_locator(ErasurePositions, CodewordCount, ErasureLocator), unknown_error_count(ErasurePositions, EccCount, UnknownErrorCount), combined_locator(UnknownErrorCount, Syndromes, ErasureLocator, _ErrorLocator, Locator), locator_error_sites(Locator, CodewordCount, Positions, XValues), length(ErasurePositions, ErasureCount), TotalCount is ErasureCount + UnknownErrorCount, length(Positions, TotalCount), erasure_positions_present(ErasurePositions, Positions), rs_error_magnitudes(TotalCount, XValues, Syndromes, Magnitudes), apply_error_corrections(Codewords, Positions, Magnitudes, CorrectedCodewords), rs_syndromes(CorrectedCodewords, EccCount, CorrectedSyndromes), all_zero(CorrectedSyndromes), pair_corrections(Positions, Magnitudes, Corrections). unknown_error_count(ErasurePositions, EccCount, UnknownErrorCount) :- length(ErasurePositions, ErasureCount), RemainingCapacity is EccCount - ErasureCount, RemainingCapacity >= 0, MaxUnknownErrors is RemainingCapacity // 2, qr_between(0, MaxUnknownErrors, UnknownErrorCount). combined_locator(0, _Syndromes, ErasureLocator, [1], ErasureLocator). combined_locator(UnknownErrorCount, Syndromes, ErasureLocator, ErrorLocator, Locator) :- UnknownErrorCount > 0, modified_syndromes(Syndromes, ErasureLocator, ModifiedSyndromes), rs_locator(UnknownErrorCount, ModifiedSyndromes, ErrorLocator), poly_mul_asc(ErasureLocator, ErrorLocator, Locator). erasure_locator(Positions, CodewordCount, Locator) :- erasure_locator(Positions, CodewordCount, [1], Locator). erasure_locator([], _CodewordCount, Locator, Locator). erasure_locator([Position|Positions], CodewordCount, Locator0, Locator) :- position_xvalue(Position, CodewordCount, XValue), poly_mul_asc(Locator0, [1, XValue], Locator1), erasure_locator(Positions, CodewordCount, Locator1, Locator). position_xvalue(Position, CodewordCount, XValue) :- Power is CodewordCount - 1 - Position, gf_alpha_power(Power, XValue). modified_syndromes(Syndromes, [_Only], Syndromes) :- !. % modified_syndromes/3 folds the erasure locator into the syndrome sequence so % the unknown-error locator can be solved without re-guessing known erasures. modified_syndromes(Syndromes, ErasureLocator, ModifiedSyndromes) :- length(ErasureLocator, LocatorLength), ErasureCount is LocatorLength - 1, modified_syndromes(0, Syndromes, ErasureLocator, ErasureCount, ModifiedSyndromes). modified_syndromes(Index, Syndromes, _ErasureLocator, ErasureCount, []) :- length(Syndromes, SyndromeCount), Index >= SyndromeCount - ErasureCount, !. modified_syndromes(Index, Syndromes, ErasureLocator, ErasureCount, [Value|Values]) :- ModifiedIndex is Index + ErasureCount, locator_window_value(0, ModifiedIndex, Syndromes, ErasureLocator, 0, Value), Index1 is Index + 1, modified_syndromes(Index1, Syndromes, ErasureLocator, ErasureCount, Values). locator_window_value(CoefficientIndex, _ModifiedIndex, _Syndromes, ErasureLocator, Accumulator, Accumulator) :- length(ErasureLocator, LocatorLength), CoefficientIndex >= LocatorLength, !. locator_window_value(CoefficientIndex, ModifiedIndex, Syndromes, ErasureLocator, Accumulator0, Value) :- nth0(CoefficientIndex, ErasureLocator, Coefficient), SyndromeIndex is ModifiedIndex - CoefficientIndex, nth0(SyndromeIndex, Syndromes, Syndrome), gf_mul(Coefficient, Syndrome, Product), bxor(Accumulator0, Product, Accumulator1), CoefficientIndex1 is CoefficientIndex + 1, locator_window_value(CoefficientIndex1, ModifiedIndex, Syndromes, ErasureLocator, Accumulator1, Value). poly_mul_asc([], _Right, []). poly_mul_asc([Left|Lefts], Right, Product) :- poly_scale(Right, Left, ScaledRight), poly_mul_asc(Lefts, Right, RestProduct0), poly_prepend_zero(RestProduct0, RestProduct), poly_add_asc(ScaledRight, RestProduct, Product). poly_scale([], _Factor, []). poly_scale([Coefficient0|Coefficients0], Factor, [Coefficient|Coefficients]) :- gf_mul(Coefficient0, Factor, Coefficient), poly_scale(Coefficients0, Factor, Coefficients). poly_prepend_zero(Polynomial, [0|Polynomial]). poly_add_asc([], Polynomial, Polynomial). poly_add_asc(Polynomial, [], Polynomial). poly_add_asc([Left|Lefts], [Right|Rights], [Sum|Sums]) :- bxor(Left, Right, Sum), poly_add_asc(Lefts, Rights, Sums). erasure_positions_present([], _Positions). erasure_positions_present([Position|ErasurePositions], Positions) :- member(Position, Positions), erasure_positions_present(ErasurePositions, Positions). correction_status([], rs_ok). correction_status(Corrections, rs_corrected(Corrections)). % Extracted erasures arrive as the atom erasure. The RS routines below want a % numeric codeword list plus the positions of symbols that are known missing. received_block_erasures(ReceivedCodewords, Codewords, ErasurePositions) :- received_block_erasures(ReceivedCodewords, 0, Codewords, ErasurePositions). received_block_erasures([], _Index, [], []). received_block_erasures([Word|Words], Index, [Codeword|Codewords], ErasurePositions) :- ( Word == erasure -> Codeword = 0, ErasurePositions = [Index|RestPositions] ; Codeword = Word, ErasurePositions = RestPositions ), Index1 is Index + 1, received_block_erasures(Words, Index1, Codewords, RestPositions). rs_syndromes(Codewords, EccCount, Syndromes) :- rs_syndromes(0, EccCount, Codewords, Syndromes). rs_syndromes(Index, EccCount, _Codewords, []) :- Index >= EccCount, !. rs_syndromes(Index, EccCount, Codewords, [Syndrome|Syndromes]) :- gf_alpha_power(Index, Root), gf_poly_eval_desc(Codewords, Root, Syndrome), Index1 is Index + 1, rs_syndromes(Index1, EccCount, Codewords, Syndromes). rs_locator(ErrorCount, Syndromes, [1|Coefficients]) :- rs_locator_matrix(ErrorCount, Syndromes, Matrix), gf_linear_solve(Matrix, Coefficients). rs_locator_matrix(ErrorCount, Syndromes, Matrix) :- rs_locator_matrix(0, ErrorCount, Syndromes, Matrix). rs_locator_matrix(RowIndex, ErrorCount, _Syndromes, []) :- RowIndex >= ErrorCount, !. rs_locator_matrix(RowIndex, ErrorCount, Syndromes, [Row|Rows]) :- rs_locator_row(ErrorCount, Syndromes, RowIndex, Row), RowIndex1 is RowIndex + 1, rs_locator_matrix(RowIndex1, ErrorCount, Syndromes, Rows). rs_locator_row(ErrorCount, Syndromes, RowIndex, Row) :- K is ErrorCount + RowIndex, rs_locator_coefficients(1, ErrorCount, Syndromes, K, Coefficients), nth0(K, Syndromes, RightHandSide), append(Coefficients, [RightHandSide], Row). rs_locator_coefficients(Index, ErrorCount, _Syndromes, _K, []) :- Index > ErrorCount, !. rs_locator_coefficients(Index, ErrorCount, Syndromes, K, [Coefficient|Coefficients]) :- SyndromeIndex is K - Index, nth0(SyndromeIndex, Syndromes, Coefficient), Index1 is Index + 1, rs_locator_coefficients(Index1, ErrorCount, Syndromes, K, Coefficients). locator_error_sites(Locator, CodewordCount, Positions, XValues) :- locator_error_sites(0, CodewordCount, Locator, Positions, XValues). locator_error_sites(Power, CodewordCount, _Locator, [], []) :- Power >= CodewordCount, !. locator_error_sites(Power, CodewordCount, Locator, Positions, XValues) :- gf_alpha_power(-Power, InverseRoot), gf_poly_eval_asc(Locator, InverseRoot, Evaluation), Power1 is Power + 1, locator_error_sites(Power1, CodewordCount, Locator, RestPositions, RestXValues), ( Evaluation =:= 0 -> Position is CodewordCount - 1 - Power, gf_alpha_power(Power, XValue), Positions = [Position|RestPositions], XValues = [XValue|RestXValues] ; Positions = RestPositions, XValues = RestXValues ). rs_error_magnitudes(ErrorCount, XValues, Syndromes, Magnitudes) :- rs_magnitude_matrix(0, ErrorCount, XValues, Syndromes, Matrix), gf_linear_solve(Matrix, Magnitudes). rs_magnitude_matrix(RowIndex, ErrorCount, _XValues, _Syndromes, []) :- RowIndex >= ErrorCount, !. rs_magnitude_matrix(RowIndex, ErrorCount, XValues, Syndromes, [Row|Rows]) :- rs_magnitude_row(RowIndex, XValues, Syndromes, Row), RowIndex1 is RowIndex + 1, rs_magnitude_matrix(RowIndex1, ErrorCount, XValues, Syndromes, Rows). rs_magnitude_row(RowIndex, XValues, Syndromes, Row) :- rs_magnitude_coefficients(XValues, RowIndex, Coefficients), nth0(RowIndex, Syndromes, RightHandSide), append(Coefficients, [RightHandSide], Row). rs_magnitude_coefficients([], _Exponent, []). rs_magnitude_coefficients([XValue|XValues], Exponent, [Coefficient|Coefficients]) :- gf_power(XValue, Exponent, Coefficient), rs_magnitude_coefficients(XValues, Exponent, Coefficients). apply_error_corrections(Codewords, [], [], Codewords). apply_error_corrections(Codewords0, [Position|Positions], [Magnitude|Magnitudes], Codewords) :- apply_error_correction(Codewords0, Position, Magnitude, Codewords1), apply_error_corrections(Codewords1, Positions, Magnitudes, Codewords). apply_error_correction(Codewords0, Position, Magnitude, Codewords) :- split_at(Position, Codewords0, Prefix, [Word0|Suffix]), bxor(Word0, Magnitude, Word), append(Prefix, [Word|Suffix], Codewords). pair_corrections([], [], []). pair_corrections([Position|Positions], [Magnitude|Magnitudes], [correction(Position, Magnitude)|Corrections]) :- pair_corrections(Positions, Magnitudes, Corrections). xor_scaled_prefix(Rest, [], _Factor, Rest). xor_scaled_prefix([Word|Words], [Generator|Generators], Factor, [Result|Results]) :- gf_mul(Generator, Factor, Product), bxor(Word, Product, Result), xor_scaled_prefix(Words, Generators, Factor, Results). generator_poly(0, [1]). generator_poly(Degree, Polynomial) :- Degree > 0, generator_poly(0, Degree, [1], Polynomial). generator_poly(Index, Degree, Polynomial, Polynomial) :- Index =:= Degree, !. generator_poly(Index, Degree, Polynomial0, Polynomial) :- gf_pow(Index, AlphaPower), poly_mul_x_plus(Polynomial0, AlphaPower, Polynomial1), Index1 is Index + 1, generator_poly(Index1, Degree, Polynomial1, Polynomial). poly_mul_x_plus([Coefficient|Coefficients], Factor, [Coefficient|Products]) :- gf_mul(Coefficient, Factor, Carry), poly_mul_x_plus_rest(Coefficients, Factor, Carry, Products). poly_mul_x_plus_rest([], _Factor, Carry, [Carry]). poly_mul_x_plus_rest([Coefficient|Coefficients], Factor, CarryIn, [Product|Products]) :- bxor(Coefficient, CarryIn, Product), gf_mul(Coefficient, Factor, CarryOut), poly_mul_x_plus_rest(Coefficients, Factor, CarryOut, Products). % gf_pow/2 is just alpha^Exponent, where alpha is the QR field generator 2. % It delegates to the general repeated-squaring helper below. gf_pow(Exponent, Value) :- Exponent >= 0, gf_power(2, Exponent, Value). gf_mul(0, _B, 0). gf_mul(_A, 0, 0). gf_mul(A, B, Product) :- A > 0, B > 0, gf_mul(A, B, 0, Product). gf_mul(_A, 0, Accumulator, Accumulator). gf_mul(A, B, Accumulator, Product) :- B > 0, ( 1 is B /\ 1 -> bxor(Accumulator, A, Accumulator1) ; Accumulator1 = Accumulator ), AShift is A << 1, ( 256 =:= (AShift /\ 256) -> bxor(AShift, 285, A1) ; A1 = AShift ), B1 is B >> 1, gf_mul(A1, B1, Accumulator1, Product). gf_inv(A, Inverse) :- A > 0, gf_power(A, 254, Inverse). gf_div(A, B, Quotient) :- B > 0, gf_inv(B, Inverse), gf_mul(A, Inverse, Quotient). gf_power(_Base, 0, 1). gf_power(0, Exponent, 0) :- Exponent > 0, !. gf_power(Base, Exponent, Value) :- Exponent > 0, gf_power(Base, Exponent, 1, Value). gf_power(_Base, 0, Accumulator, Accumulator). gf_power(Base, Exponent, Accumulator0, Value) :- Exponent > 0, ( 1 is Exponent /\ 1 -> gf_mul(Accumulator0, Base, Accumulator1) ; Accumulator1 = Accumulator0 ), gf_mul(Base, Base, SquaredBase), Exponent1 is Exponent >> 1, gf_power(SquaredBase, Exponent1, Accumulator1, Value). gf_alpha_power(Exponent, Value) :- normalize_field_exponent(Exponent, NormalizedExponent), gf_pow(NormalizedExponent, Value). normalize_field_exponent(Exponent, NormalizedExponent) :- Normalized0 is Exponent mod 255, ( Normalized0 < 0 -> NormalizedExponent is Normalized0 + 255 ; NormalizedExponent = Normalized0 ). gf_poly_eval_desc(Coefficients, X, Value) :- gf_poly_eval_desc(Coefficients, X, 0, Value). gf_poly_eval_desc([], _X, Value, Value). gf_poly_eval_desc([Coefficient|Coefficients], X, Accumulator0, Value) :- gf_mul(Accumulator0, X, Product), bxor(Product, Coefficient, Accumulator1), gf_poly_eval_desc(Coefficients, X, Accumulator1, Value). gf_poly_eval_asc(Coefficients, X, Value) :- reverse(Coefficients, Descending), gf_poly_eval_desc(Descending, X, Value). % The matrix is in augmented-row form over GF(256): each row is coefficients % followed by the right-hand side, and Gaussian elimination leaves the % solution in the last column. gf_linear_solve(Matrix, Solution) :- length(Matrix, VariableCount), gf_gauss_jordan(0, VariableCount, Matrix, ReducedMatrix), solution_column(ReducedMatrix, Solution). gf_gauss_jordan(Column, VariableCount, Matrix, Matrix) :- Column >= VariableCount, !. gf_gauss_jordan(Column, VariableCount, Matrix0, Matrix) :- split_at(Column, Matrix0, CompletedRows0, PendingRows0), pivot_row(Column, PendingRows0, PivotRow0, PendingRows1), nth0(Column, PivotRow0, Pivot), gf_inv(Pivot, PivotInverse), gf_scale_row(PivotRow0, PivotInverse, PivotRow), gf_eliminate_rows(CompletedRows0, Column, PivotRow, CompletedRows), gf_eliminate_rows(PendingRows1, Column, PivotRow, PendingRows), append(CompletedRows, [PivotRow|PendingRows], Matrix1), Column1 is Column + 1, gf_gauss_jordan(Column1, VariableCount, Matrix1, Matrix). pivot_row(Column, [Row|Rows], Row, Rows) :- nth0(Column, Row, Pivot), Pivot =\= 0, !. pivot_row(Column, [Row|Rows0], PivotRow, [Row|Rows]) :- pivot_row(Column, Rows0, PivotRow, Rows). gf_scale_row([], _Factor, []). gf_scale_row([Value0|Values0], Factor, [Value|Values]) :- gf_mul(Value0, Factor, Value), gf_scale_row(Values0, Factor, Values). gf_eliminate_rows([], _Column, _PivotRow, []). gf_eliminate_rows([Row0|Rows0], Column, PivotRow, [Row|Rows]) :- nth0(Column, Row0, Factor), ( Factor =:= 0 -> Row = Row0 ; gf_scale_row(PivotRow, Factor, ScaledPivot), gf_row_xor(Row0, ScaledPivot, Row) ), gf_eliminate_rows(Rows0, Column, PivotRow, Rows). gf_row_xor([], [], []). gf_row_xor([Left0|Lefts0], [Right0|Rights0], [Value|Values]) :- bxor(Left0, Right0, Value), gf_row_xor(Lefts0, Rights0, Values). solution_column([], []). solution_column([Row|Rows], [Value|Values]) :- last_element(Row, Value), solution_column(Rows, Values). last_element([Value], Value). last_element([_Value|Values], Last) :- last_element(Values, Last). bxor(A, B, X) :- X is (A \/ B) /\ \(A /\ B). %% Format information % % The format word encodes the EC level and mask. On decode we match the % observed modules against the set of valid format patterns so partial grids % and small BCH-correctable damage can still be decoded. level_format_bits(l, 1). level_format_bits(m, 0). level_format_bits(q, 3). level_format_bits(h, 2). format_bits(Level, Mask, Bits) :- level_format_bits(Level, LevelBits), Data is (LevelBits << 3) \/ Mask, Shifted is Data << 10, bch_remainder(Shifted, 1335, Remainder), % 0x537 RawFormat is Shifted \/ Remainder, bxor(RawFormat, 21522, FormatValue), % 0x5412 int_bits(FormatValue, 15, BigEndianBits), reverse(BigEndianBits, Bits). read_format_bits(Grid, Level, Mask, Bits) :- grid_version(Grid, Version), format_positions_primary(PositionsPrimary), format_positions_secondary(Version, PositionsSecondary), positions_bits(Grid, PositionsPrimary, ObservedPrimary), positions_bits(Grid, PositionsSecondary, ObservedSecondary), select_level(Level), select_mask(Mask), format_bits(Level, Mask, Bits), format_observation_distance(ObservedPrimary, Bits, PrimaryKnownCount, PrimaryDistance), format_observation_distance(ObservedSecondary, Bits, SecondaryKnownCount, SecondaryDistance), format_bits_candidate(PrimaryKnownCount, PrimaryDistance, SecondaryKnownCount, SecondaryDistance). format_observation_distance(ObservedBits, Bits, KnownCount, Distance) :- format_observation_distance(ObservedBits, Bits, 0, KnownCount, 0, Distance). format_observation_distance([], [], KnownCount, KnownCount, Distance, Distance). format_observation_distance([ObservedBit|ObservedBits], [Bit|Bits], KnownCount0, KnownCount, Distance0, Distance) :- ( ObservedBit == u -> KnownCount1 = KnownCount0, Distance1 = Distance0 ; KnownCount1 is KnownCount0 + 1, ( ObservedBit =:= Bit -> Distance1 = Distance0 ; Distance1 is Distance0 + 1 ) ), format_observation_distance(ObservedBits, Bits, KnownCount1, KnownCount, Distance1, Distance). format_bits_candidate(PrimaryKnownCount, PrimaryDistance, SecondaryKnownCount, SecondaryDistance) :- ( PrimaryKnownCount =:= 0, SecondaryKnownCount =:= 0 ; PrimaryKnownCount > 0, PrimaryDistance =< 3 ; SecondaryKnownCount > 0, SecondaryDistance =< 3 ). bch_remainder(Value, Generator, Remainder) :- bit_length(Generator, GeneratorLength), bch_reduce(Value, Generator, GeneratorLength, Remainder). bch_reduce(Value, Generator, GeneratorLength, Remainder) :- bit_length(Value, ValueLength), ( ValueLength < GeneratorLength -> Remainder = Value ; Shift is ValueLength - GeneratorLength, ShiftedGenerator is Generator << Shift, bxor(Value, ShiftedGenerator, Value1), bch_reduce(Value1, Generator, GeneratorLength, Remainder) ). bit_length(0, 0). bit_length(Value, Length) :- Value > 0, bit_length(Value, 0, Length). bit_length(0, Length, Length). bit_length(Value, Accumulator, Length) :- Value > 0, Value1 is Value >> 1, Accumulator1 is Accumulator + 1, bit_length(Value1, Accumulator1, Length). %% QR board construction % % The board starts as all data cells, then the fixed function patterns are % written in the same order they are usually explained in QR references: % finders, separators, alignment patterns, timing patterns, dark module, and % finally reserved format/version areas. template_board(Version, Board) :- version_size(Version, Size), blank_board(Size, Board0), place_finders(Board0, Board1), place_separators(Board1, Board2), place_alignment_patterns(Board2, Version, Board3), place_timing_patterns(Board3, Board4), place_dark_module(Board4, Version, Board5), reserve_format_modules(Board5, Version, Board6), reserve_version_modules(Board6, Version, Board). blank_board(Size, Board) :- blank_rows(Size, Size, Board). blank_rows(0, _Size, []). blank_rows(Count, Size, [Row|Rows]) :- Count > 0, blank_row(Size, Row), Count1 is Count - 1, blank_rows(Count1, Size, Rows). blank_row(0, []). blank_row(Count, [cell(data, unset)|Cells]) :- Count > 0, Count1 is Count - 1, blank_row(Count1, Cells). place_finders(Board0, Board) :- length(Board0, Size), Edge is Size - 7, place_finder(Board0, 0, 0, Board1), place_finder(Board1, 0, Edge, Board2), place_finder(Board2, Edge, 0, Board). place_finder(Board0, Top, Left, Board) :- finder_cells(Top, Left, Cells), place_cells(Board0, Cells, Board). finder_cells(Top, Left, Cells) :- findall(cell_at(Row, Col, function, Value), ( qr_between(0, 6, DeltaRow), qr_between(0, 6, DeltaCol), Row is Top + DeltaRow, Col is Left + DeltaCol, finder_value(DeltaRow, DeltaCol, Value) ), Cells). finder_value(Row, Col, 1) :- ( Row =:= 0 ; Row =:= 6 ; Col =:= 0 ; Col =:= 6 ; (Row >= 2, Row =< 4, Col >= 2, Col =< 4) ), !. finder_value(_Row, _Col, 0). place_separators(Board0, Board) :- length(Board0, Size), findall(cell_at(Row, Col, function, 0), separator_position(Size, Row, Col), Cells), place_cells(Board0, Cells, Board). separator_position(_Size, 7, Col) :- qr_between(0, 7, Col). separator_position(_Size, Row, 7) :- qr_between(0, 7, Row). separator_position(Size, 7, Col) :- Start is Size - 8, End is Size - 1, qr_between(Start, End, Col). separator_position(Size, Row, Col) :- Col is Size - 8, qr_between(0, 7, Row). separator_position(Size, Row, Col) :- Row is Size - 8, qr_between(0, 7, Col). separator_position(Size, Row, 7) :- Start is Size - 8, End is Size - 1, qr_between(Start, End, Row). place_alignment_patterns(Board0, Version, Board) :- alignment_centers(Version, Centers), findall(cell_at(Row, Col, function, Value), alignment_cell(Board0, Centers, Row, Col, Value), Cells), place_cells(Board0, Cells, Board). alignment_cell(Board, Centers, Row, Col, Value) :- member(RowCenter, Centers), member(ColCenter, Centers), board_cell(Board, RowCenter, ColCenter, cell(data, unset)), qr_between(-2, 2, DeltaRow), qr_between(-2, 2, DeltaCol), Row is RowCenter + DeltaRow, Col is ColCenter + DeltaCol, alignment_value(DeltaRow, DeltaCol, Value). alignment_value(DeltaRow, DeltaCol, 1) :- ( DeltaRow =:= -2 ; DeltaRow =:= 2 ; DeltaCol =:= -2 ; DeltaCol =:= 2 ; (DeltaRow =:= 0, DeltaCol =:= 0) ), !. alignment_value(_DeltaRow, _DeltaCol, 0). place_timing_patterns(Board0, Board) :- length(Board0, Size), findall(cell_at(6, Col, function, Value), timing_position(Board0, Size, Col, Value), RowCells), place_cells(Board0, RowCells, Board1), findall(cell_at(Row, 6, function, Value), timing_position_vertical(Board1, Size, Row, Value), ColCells), place_cells(Board1, ColCells, Board). timing_position(Board, Size, Index, Value) :- End is Size - 9, qr_between(8, End, Index), board_cell(Board, 6, Index, cell(data, unset)), timing_bit(Index, Value). timing_position_vertical(Board, Size, Index, Value) :- End is Size - 9, qr_between(8, End, Index), board_cell(Board, Index, 6, cell(data, unset)), timing_bit(Index, Value). timing_bit(Index, Bit) :- integer(Index), Parity is Index mod 2, ( Parity =:= 0 -> Bit = 1 ; Bit = 0 ). place_dark_module(Board0, Version, Board) :- version_size(Version, Size), Row is Size - 8, set_module(Board0, Row, 8, function, 1, Board). reserve_format_modules(Board0, Version, Board) :- format_positions_primary(Primary), format_positions_secondary(Version, Secondary), reserve_positions(Board0, Primary, Board1), reserve_positions(Board1, Secondary, Board). reserve_version_modules(Board, Version, Board) :- Version < 7, !. reserve_version_modules(Board0, Version, Board) :- version_positions(Version, Positions), reserve_positions(Board0, Positions, Board). reserve_positions(Board, [], Board). reserve_positions(Board0, [pos(_Index, Row, Col)|Positions], Board) :- set_module(Board0, Row, Col, function, unset, Board1), reserve_positions(Board1, Positions, Board). format_positions_primary( [ pos(0, 0, 8), pos(1, 1, 8), pos(2, 2, 8), pos(3, 3, 8), pos(4, 4, 8), pos(5, 5, 8), pos(6, 7, 8), pos(7, 8, 8), pos(8, 8, 7), pos(9, 8, 5), pos(10, 8, 4), pos(11, 8, 3), pos(12, 8, 2), pos(13, 8, 1), pos(14, 8, 0) ]). format_positions_secondary(Version, Positions) :- version_size(Version, Size), findall(pos(Index, Row, Col), format_secondary_position(Size, Index, Row, Col), Positions). format_secondary_position(Size, Index, 8, Col) :- qr_between(0, 7, Index), Col is Size - 1 - Index. format_secondary_position(Size, Index, Row, 8) :- qr_between(8, 14, Index), Row is Size + Index - 15. place_format_bits(Board0, Version, Bits, Board) :- format_positions_primary(Primary), format_positions_secondary(Version, Secondary), place_bit_positions(Board0, Primary, Bits, Board1), place_bit_positions(Board1, Secondary, Bits, Board). place_version_bits(Board, Version, Board) :- Version < 7, !. place_version_bits(Board0, Version, Board) :- version_bits(Version, Bits), version_positions(Version, Positions), place_bit_positions(Board0, Positions, Bits, Board). version_bits(Version, Bits) :- Version >= 7, Version =< 40, Shifted is Version << 12, bch_remainder(Shifted, 7973, Remainder), % 0x1f25 VersionValue is Shifted \/ Remainder, int_bits(VersionValue, 18, BigEndianBits), reverse(BigEndianBits, Bits). version_positions(Version, Positions) :- version_size(Version, Size), Start is Size - 11, findall(pos(Index, Row, Col), version_primary_position(Index, Start, Row, Col), Primary), findall(pos(Index, Row, Col), version_secondary_position(Index, Start, Row, Col), Secondary), append(Primary, Secondary, Positions). version_primary_position(Index, Start, Row, Col) :- qr_between(0, 17, Index), Row is Index // 3, Col is Start + (Index mod 3). version_secondary_position(Index, Start, Row, Col) :- qr_between(0, 17, Index), Row is Start + (Index mod 3), Col is Index // 3. place_bit_positions(Board, [], _Bits, Board). place_bit_positions(Board0, [pos(Index, Row, Col)|Positions], Bits, Board) :- nth0(Index, Bits, Bit), set_module(Board0, Row, Col, function, Bit, Board1), place_bit_positions(Board1, Positions, Bits, Board). positions_bits(_Grid, [], []). positions_bits(Grid, [pos(_Index, Row, Col)|Positions], [Bit|Bits]) :- grid_observed_bit(Grid, Row, Col, Bit), positions_bits(Grid, Positions, Bits). %% Data placement and extraction % % Data modules follow the QR zig-zag walk through two-column stripes from right % to left, skipping the timing column. This section implements that walk once % and reuses it in both directions. place_data_bits(Board0, Bits, Board) :- data_positions(Board0, Positions), same_length(Bits, Positions), place_data_positions(Board0, Positions, Bits, Board). place_data_positions(Board, [], [], Board). place_data_positions(Board0, [cell_at(Row, Col, data, _)|Positions], [Bit|Bits], Board) :- set_module(Board0, Row, Col, data, Bit, Board1), place_data_positions(Board1, Positions, Bits, Board). extract_data_bits(Grid, TemplateBoard, Mask, Bits) :- data_positions(TemplateBoard, Positions), extract_positions_bits(Grid, Positions, Mask, Bits). extract_positions_bits(_Grid, [], _Mask, []). extract_positions_bits(Grid, [cell_at(Row, Col, data, _)|Positions], Mask, [Bit|Bits]) :- grid_observed_bit(Grid, Row, Col, MaskedBit), unmask_data_bit(Mask, Row, Col, MaskedBit, Bit), extract_positions_bits(Grid, Positions, Mask, Bits). unmask_data_bit(_Mask, _Row, _Col, u, u) :- !. unmask_data_bit(Mask, Row, Col, MaskedBit, Bit) :- ( mask_bit(Mask, Row, Col) -> bit_flip(MaskedBit, Bit) ; Bit = MaskedBit ). data_positions(Board, Positions) :- length(Board, Size), StartColumn is Size - 1, zigzag_columns(StartColumn, up, Board, Positions). zigzag_columns(Column, _Direction, _Board, []) :- Column =< 0, !. zigzag_columns(Column0, Direction, Board, Positions) :- data_column(Column0, Column), pair_positions(Column, Direction, Board, PairPositions), NextColumn is Column - 2, next_direction(Direction, NextDirection), zigzag_columns(NextColumn, NextDirection, Board, RestPositions), append(PairPositions, RestPositions, Positions). data_column(6, 5) :- !. data_column(Column, Column). next_direction(up, down). next_direction(down, up). pair_positions(Column, Direction, Board, Positions) :- length(Board, Size), LastRow is Size - 1, rows_in_direction(Direction, LastRow, Rows), findall(cell_at(Row, Col, data, unset), ( member(Row, Rows), pair_column(Column, Col), board_cell(Board, Row, Col, cell(data, unset)) ), Positions). pair_column(Column, Column). pair_column(Column, Col) :- Col is Column - 1. rows_in_direction(up, LastRow, Rows) :- descending(LastRow, Rows). rows_in_direction(down, LastRow, Rows) :- ascending(0, LastRow, Rows). ascending(End, End, [End]). ascending(Start, End, [Start|Rest]) :- Start < End, Start1 is Start + 1, ascending(Start1, End, Rest). descending(Start, [Start|Rest]) :- Start > 0, Start1 is Start - 1, descending(Start1, Rest). descending(0, [0]). %% Masking % % Masking is a purely visual balancing step: it flips selected data modules so % the final matrix is easier for scanners to read without changing the payload. apply_mask(Board0, Mask, Board) :- mask_rows(Board0, Mask, 0, Board). mask_rows([], _Mask, _RowIndex, []). mask_rows([Row|Rows], Mask, RowIndex, [MaskedRow|MaskedRows]) :- mask_row(Row, Mask, RowIndex, 0, MaskedRow), NextRow is RowIndex + 1, mask_rows(Rows, Mask, NextRow, MaskedRows). mask_row([], _Mask, _RowIndex, _ColIndex, []). mask_row([Cell|Cells], Mask, RowIndex, ColIndex, [MaskedCell|MaskedCells]) :- mask_cell(Cell, Mask, RowIndex, ColIndex, MaskedCell), NextCol is ColIndex + 1, mask_row(Cells, Mask, RowIndex, NextCol, MaskedCells). mask_cell(cell(function, Value), _Mask, _RowIndex, _ColIndex, cell(function, Value)). mask_cell(cell(data, Bit), Mask, RowIndex, ColIndex, cell(data, MaskedBit)) :- ( mask_bit(Mask, RowIndex, ColIndex) -> bit_flip(Bit, MaskedBit) ; MaskedBit = Bit ). mask_bit(0, Row, Col) :- 0 is (Row + Col) mod 2. mask_bit(1, Row, _Col) :- 0 is Row mod 2. mask_bit(2, _Row, Col) :- 0 is Col mod 3. mask_bit(3, Row, Col) :- 0 is (Row + Col) mod 3. mask_bit(4, Row, Col) :- 0 is ((Row div 2) + (Col div 3)) mod 2. mask_bit(5, Row, Col) :- 0 is ((Row * Col) mod 2 + (Row * Col) mod 3). mask_bit(6, Row, Col) :- 0 is (((Row * Col) mod 2 + (Row * Col) mod 3) mod 2). mask_bit(7, Row, Col) :- 0 is (((Row + Col) mod 2 + (Row * Col) mod 3) mod 2). bit_flip(0, 1). bit_flip(1, 0). %% qr_penalty(+Grid, -Penalty) is semidet. % % Apply the standard QR mask-selection penalty rules to a finished matrix. qr_penalty(Grid, Penalty) :- penalty_evaluation_grid(Grid, EvaluationGrid), qr_raw_penalty(EvaluationGrid, Penalty), !. qr_raw_penalty(Grid, Penalty) :- qr_run_penalty(Grid, RunPenalty), qr_block_penalty(Grid, BlockPenalty), qr_finder_penalty(Grid, FinderPenalty), qr_balance_penalty(Grid, BalancePenalty), Penalty is RunPenalty + BlockPenalty + FinderPenalty + BalancePenalty. %% qr_penalty_breakdown(+Grid, -Breakdown) is semidet. % % Return the four standard QR penalty components plus their total. qr_penalty_breakdown(Grid, Breakdown) :- penalty_evaluation_grid(Grid, EvaluationGrid), qr_run_penalty(EvaluationGrid, RunPenalty), qr_block_penalty(EvaluationGrid, BlockPenalty), qr_finder_penalty(EvaluationGrid, FinderPenalty), qr_balance_penalty(EvaluationGrid, BalancePenalty), TotalPenalty is RunPenalty + BlockPenalty + FinderPenalty + BalancePenalty, Breakdown = [ runs(RunPenalty), blocks(BlockPenalty), finders(FinderPenalty), balance(BalancePenalty), total(TotalPenalty) ], !. penalty_evaluation_grid(Grid, EvaluationGrid) :- grid_version(Grid, Version), evaluation_positions(Version, Positions), clear_grid_positions(Grid, Positions, EvaluationGrid). evaluation_positions(Version, Positions) :- format_positions_primary(Primary), format_positions_secondary(Version, Secondary), append(Primary, Secondary, FormatPositions), evaluation_version_positions(Version, VersionPositions), dark_module_position(Version, DarkModule), append(FormatPositions, VersionPositions, Positions0), append(Positions0, [DarkModule], Positions). evaluation_version_positions(Version, Positions) :- Version < 7, !, Positions = []. evaluation_version_positions(Version, Positions) :- version_positions(Version, Positions). dark_module_position(Version, pos(dark_module, Row, 8)) :- version_size(Version, Size), Row is Size - 8. clear_grid_positions(Grid, [], Grid). clear_grid_positions(Grid0, [pos(_Index, Row, Col)|Positions], Grid) :- set_grid_bit(Grid0, Row, Col, 0, Grid1), clear_grid_positions(Grid1, Positions, Grid). qr_run_penalty(Grid, Penalty) :- maplist(line_run_penalty, Grid, RowPenalties), grid_columns(Grid, Columns), maplist(line_run_penalty, Columns, ColumnPenalties), append(RowPenalties, ColumnPenalties, Penalties), sum_lengths(Penalties, Penalty). line_run_penalty([Bit|Bits], Penalty) :- line_run_penalty(Bits, Bit, 1, 0, Penalty). line_run_penalty([], _Bit, RunLength, Penalty0, Penalty) :- run_length_penalty(RunLength, RunPenalty), Penalty is Penalty0 + RunPenalty. line_run_penalty([Bit|Bits], PreviousBit, RunLength, Penalty0, Penalty) :- ( Bit =:= PreviousBit -> RunLength1 is RunLength + 1, line_run_penalty(Bits, Bit, RunLength1, Penalty0, Penalty) ; run_length_penalty(RunLength, RunPenalty), Penalty1 is Penalty0 + RunPenalty, line_run_penalty(Bits, Bit, 1, Penalty1, Penalty) ). run_length_penalty(RunLength, Penalty) :- RunLength >= 5, !, Penalty is RunLength - 2. run_length_penalty(_RunLength, 0). qr_block_penalty([_Row], 0). qr_block_penalty([Row0,Row1|Rows], Penalty) :- adjacent_block_penalty(Row0, Row1, RowPenalty), qr_block_penalty([Row1|Rows], RestPenalty), Penalty is RowPenalty + RestPenalty. adjacent_block_penalty([_Bit], [_Bit0], 0). adjacent_block_penalty([Bit0,Bit1|Bits0], [Bit2,Bit3|Bits1], Penalty) :- square_block_penalty(Bit0, Bit1, Bit2, Bit3, SquarePenalty), adjacent_block_penalty([Bit1|Bits0], [Bit3|Bits1], RestPenalty), Penalty is SquarePenalty + RestPenalty. square_block_penalty(Bit, Bit, Bit, Bit, 3) :- !. square_block_penalty(_Bit0, _Bit1, _Bit2, _Bit3, 0). qr_finder_penalty(Grid, Penalty) :- maplist(line_finder_penalty, Grid, RowPenalties), grid_columns(Grid, Columns), maplist(line_finder_penalty, Columns, ColumnPenalties), append(RowPenalties, ColumnPenalties, Penalties), sum_lengths(Penalties, Penalty). line_finder_penalty(Line, Penalty) :- length(Line, Size), zeros(7, History0), line_finder_penalty(Line, Size, 0, 0, History0, 0, Penalty). line_finder_penalty([], Size, RunColor, RunLength, History0, Penalty0, Penalty) :- finder_terminate_penalty(RunColor, RunLength, History0, Size, FinderCount), Penalty is Penalty0 + FinderCount * 40. line_finder_penalty([Bit|Bits], Size, RunColor, RunLength0, History0, Penalty0, Penalty) :- ( Bit =:= RunColor -> RunLength1 is RunLength0 + 1, line_finder_penalty(Bits, Size, RunColor, RunLength1, History0, Penalty0, Penalty) ; finder_add_history(RunLength0, History0, Size, History1), ( RunColor =:= 0 -> finder_history_patterns(History1, FinderCount) ; FinderCount = 0 ), Penalty1 is Penalty0 + FinderCount * 40, line_finder_penalty(Bits, Size, Bit, 1, History1, Penalty1, Penalty) ). finder_terminate_penalty(RunColor, RunLength, History0, Size, FinderCount) :- ( RunColor =:= 1 -> finder_add_history(RunLength, History0, Size, History1), FinalLightRun0 = 0 ; History1 = History0, FinalLightRun0 = RunLength ), FinalLightRun is FinalLightRun0 + Size, finder_add_history(FinalLightRun, History1, Size, History), finder_history_patterns(History, FinderCount). finder_add_history(RunLength0, History0, Size, History) :- History0 = [Newest|_], ( Newest =:= 0 -> RunLength is RunLength0 + Size ; RunLength = RunLength0 ), push_run_history(RunLength, History0, History). push_run_history(RunLength, [H0,H1,H2,H3,H4,H5,_H6], [RunLength,H0,H1,H2,H3,H4,H5]). finder_history_patterns([LeftNew, N, Run2, Run3, Run4, Run5, RightOld], Count) :- ( N > 0, Run2 =:= N, Run4 =:= N, Run5 =:= N, Run3 =:= N * 3 -> finder_pattern_count(LeftNew, RightOld, N, Count) ; Count = 0 ). finder_pattern_count(LeftNew, RightOld, N, Count) :- ( LeftNew >= N * 4, RightOld >= N -> Count0 = 1 ; Count0 = 0 ), ( RightOld >= N * 4, LeftNew >= N -> Count1 = 1 ; Count1 = 0 ), Count is Count0 + Count1. qr_balance_penalty(Grid, Penalty) :- grid_size(Grid, Size), TotalModules is Size * Size, dark_module_count(Grid, DarkModules), DeviationNumerator is abs(DarkModules * 20 - TotalModules * 10), PenaltySteps is ((DeviationNumerator + TotalModules - 1) // TotalModules) - 1, Penalty is PenaltySteps * 10. dark_module_count([], 0). dark_module_count([Row|Rows], Count) :- dark_row_count(Row, RowCount), dark_module_count(Rows, RestCount), Count is RowCount + RestCount. dark_row_count([], 0). dark_row_count([1|Bits], Count) :- dark_row_count(Bits, RestCount), Count is RestCount + 1. dark_row_count([0|Bits], Count) :- dark_row_count(Bits, Count). grid_columns([[]|_Rows], []). grid_columns(Rows, [Column|Columns]) :- take_first_column(Rows, Column, RestRows), grid_columns(RestRows, Columns). take_first_column([], [], []). take_first_column([[Value|Values]|Rows], [Value|Column], [Values|RestRows]) :- take_first_column(Rows, Column, RestRows). %% Matrix helpers % % These predicates are intentionally simple list manipulations so the board % transformations above stay easy to follow for someone learning Prolog. place_cells(Board, [], Board). place_cells(Board0, [cell_at(Row, Col, Role, Value)|Cells], Board) :- set_module(Board0, Row, Col, Role, Value, Board1), place_cells(Board1, Cells, Board). set_module(Board0, Row, Col, Role, Value, Board) :- set_cell(Board0, Row, Col, cell(Role, Value), Board). set_cell([Row|Rows], 0, Col, Cell, [Row1|Rows]) :- set_cell_in_row(Row, Col, Cell, Row1). set_cell([Row|Rows], RowIndex, Col, Cell, [Row|Rows1]) :- RowIndex > 0, NextRow is RowIndex - 1, set_cell(Rows, NextRow, Col, Cell, Rows1). set_cell_in_row([_Cell|Cells], 0, Cell, [Cell|Cells]). set_cell_in_row([Cell0|Cells], ColIndex, Cell, [Cell0|Cells1]) :- ColIndex > 0, NextCol is ColIndex - 1, set_cell_in_row(Cells, NextCol, Cell, Cells1). board_cell(Board, Row, Col, Cell) :- nth0(Row, Board, BoardRow), nth0(Col, BoardRow, Cell). board_view(Board, View) :- maplist(row_view, Board, View). row_view(Row, View) :- maplist(cell_view_value, Row, View). cell_view_value(cell(_Role, unset), u). cell_view_value(cell(_Role, Value), Value) :- Value \== unset. board_bits(Board, Grid) :- maplist(row_bits, Board, Grid). row_bits(Row, Bits) :- maplist(cell_bit_value, Row, Bits). cell_bit_value(cell(_Role, Bit), Bit) :- integer(Bit). grid_size(Grid, Size) :- length(Grid, Size), maplist(same_length_list(Size), Grid). same_length_list(Size, Row) :- length(Row, Size). grid_observed_bit(Grid, Row, Col, Bit) :- nth0(Row, Grid, GridRow), nth0(Col, GridRow, Cell), observed_grid_value(Cell, Bit). observed_grid_value(Cell, Bit) :- binary_bit(Cell), !, Bit = Cell. observed_grid_value(Cell, u) :- var(Cell), !. observed_grid_value(u, u). fill_unknown_grid_cells(ObservedRows, CorrectedRows) :- maplist(fill_unknown_row_cells, ObservedRows, CorrectedRows). fill_unknown_row_cells(ObservedCells, CorrectedCells) :- maplist(fill_unknown_cell, ObservedCells, CorrectedCells). fill_unknown_cell(Cell, Bit) :- var(Cell), !, Cell = Bit. % Explicit u markers are left untouched; they act as readable wildcards rather % than output variables. fill_unknown_cell(_Cell, _Bit). %% Bit, word, and text helpers % % This section collects the small relations shared everywhere else: character % normalization, integer <-> bit list conversion, and byte packing. text_codes(Text, Codes) :- var(Text), !, codes_text(Codes, Text). text_codes(Text, Codes) :- atom(Text), !, atom_codes(Text, Codes). text_codes(Text, Codes) :- proper_list(Text), !, list_codes(Text, Codes). codes_text(Codes, Text) :- codes_atoms(Codes, Text). list_codes([], []). list_codes([Item|Items], [Code|Codes]) :- item_code(Item, Code), list_codes(Items, Codes). item_code(Item, Item) :- integer(Item), !. item_code(Item, Code) :- atom(Item), atom_length(Item, 1), char_code(Item, Code). codes_atoms([], []). codes_atoms([Code|Codes], [Atom|Atoms]) :- atom_codes(Atom, [Code]), codes_atoms(Codes, Atoms). proper_list([]). proper_list([_Item|Items]) :- proper_list(Items). int_bits(_Value, 0, []) :- !. int_bits(Value, Width, [Bit|Bits]) :- Width > 0, Shift is Width - 1, Bit is (Value >> Shift) /\ 1, Width1 is Width - 1, int_bits(Value, Width1, Bits). bits_int(Bits, Value) :- bits_int(Bits, 0, Value). bits_int([], Value, Value). bits_int([Bit|Bits], Accumulator, Value) :- Accumulator1 is (Accumulator << 1) \/ Bit, bits_int(Bits, Accumulator1, Value). bits_codewords([], []). bits_codewords(Bits, [Word|Words]) :- split_at(8, Bits, ByteBits, RestBits), bits_int(ByteBits, Word), bits_codewords(RestBits, Words). bits_received_codewords([], []). bits_received_codewords(Bits, [Word|Words]) :- split_at(8, Bits, ByteBits, RestBits), received_byte_word(ByteBits, Word), bits_received_codewords(RestBits, Words). received_byte_word(ByteBits, Word) :- ( all_known_bits(ByteBits) -> bits_int(ByteBits, Word) ; Word = erasure ). all_known_bits([]). all_known_bits([Bit|Bits]) :- binary_bit(Bit), all_known_bits(Bits). codewords_bits([], []). codewords_bits([Word|Words], Bits) :- int_bits(Word, 8, ByteBits), codewords_bits(Words, RestBits), append(ByteBits, RestBits, Bits). split_at(0, List, [], List) :- !. split_at(Count, [Item|Items], [Item|Prefix], Rest) :- Count > 0, Count1 is Count - 1, split_at(Count1, Items, Prefix, Rest). zeros(0, []). zeros(Count, [0|Zeros]) :- Count > 0, Count1 is Count - 1, zeros(Count1, Zeros). min_int(A, B, A) :- A =< B, !. min_int(_A, B, B). max_int(A, B, A) :- A >= B, !. max_int(_A, B, B). abs_int(Value, AbsValue) :- Value >= 0, !, AbsValue = Value. abs_int(Value, AbsValue) :- AbsValue is -Value. qr_between(Low, High, Value) :- integer(Low), integer(High), Low =< High, ( var(Value) -> qr_between_enum(Low, High, Value) ; integer(Value), Value >= Low, Value =< High ). qr_between_enum(Low, _High, Low). qr_between_enum(Low, High, Value) :- Low < High, Low1 is Low + 1, qr_between_enum(Low1, High, Value). int_digits(WidthValue, Width, Digits) :- int_digits_rev(WidthValue, Width, DigitsRev), reverse(DigitsRev, Digits). int_digits_rev(_Value, 0, []). int_digits_rev(Value, Width, [Digit|Digits]) :- Width > 0, Digit is Value mod 10, Value1 is Value div 10, Width1 is Width - 1, int_digits_rev(Value1, Width1, Digits). digits_to_codes([], []). digits_to_codes([Digit|Digits], [Code|Codes]) :- Code is Digit + 0'0, digits_to_codes(Digits, Codes). %% Rendering helpers % % Rendering is intentionally separate from encoding. The public relation % produces pure 0/1 grids; these helpers only turn them into terminal-friendly % Unicode blocks. % % The compact renderer pairs two QR rows into one terminal row: % - top 1, bottom 1 -> full block % - top 1, bottom 0 -> upper half block % - top 0, bottom 1 -> lower half block % - top 0, bottom 0 -> space % % This is the same general idea used by tools such as qrencode's UTF-8 output. add_quiet_zone_rows(0, _Row, []). add_quiet_zone_rows(Count, Row, [Row|Rows]) :- Count > 0, Count1 is Count - 1, add_quiet_zone_rows(Count1, Row, Rows). add_quiet_zone_cols(Row, QuietRow) :- zeros(4, Quiet), append(Quiet, Row, Middle), append(Middle, Quiet, QuietRow). render_half_rows([], []). render_half_rows([TopRow, BottomRow|Rows], [Line|Lines]) :- render_half_row(TopRow, BottomRow, Line), render_half_rows(Rows, Lines). render_half_rows([TopRow], [Line]) :- row_zeros(TopRow, BottomRow), render_half_row(TopRow, BottomRow, Line). row_zeros(Row, Zeros) :- length(Row, Width), zeros(Width, Zeros). render_half_row([], [], []). render_half_row([Top|TopBits], [Bottom|BottomBits], [Code|Codes]) :- half_block_code(Top, Bottom, Code), render_half_row(TopBits, BottomBits, Codes). half_block_code(1, 1, 9608). half_block_code(1, 0, 9600). half_block_code(0, 1, 9604). half_block_code(0, 0, 32). render_wide_row(Row, Line) :- render_wide_row(Row, [], Line). render_wide_row([], Line, Line). render_wide_row([1|Bits], Line0, Line) :- append(Line0, "██", Line1), render_wide_row(Bits, Line1, Line). render_wide_row([0|Bits], Line0, Line) :- append(Line0, " ", Line1), render_wide_row(Bits, Line1, Line). write_lines([]). write_lines([Line|Lines]) :- write_text(Line), nl, write_lines(Lines). write_text([]). write_text([Item|Items]) :- write_text_item(Item), write_text(Items). write_text_item(Item) :- integer(Item), !, put_code(Item). write_text_item(Item) :- put_char(Item). %% Static QR tables % % The remainder of the file is mostly specification data: alignment pattern % centers, Kanji mappings, and RS block layout tables for all versions. alignment_centers(1, []). alignment_centers(2, [6, 18]). alignment_centers(3, [6, 22]). alignment_centers(4, [6, 26]). alignment_centers(5, [6, 30]). alignment_centers(6, [6, 34]). alignment_centers(7, [6, 22, 38]). alignment_centers(8, [6, 24, 42]). alignment_centers(9, [6, 26, 46]). alignment_centers(10, [6, 28, 50]). alignment_centers(11, [6, 30, 54]). alignment_centers(12, [6, 32, 58]). alignment_centers(13, [6, 34, 62]). alignment_centers(14, [6, 26, 46, 66]). alignment_centers(15, [6, 26, 48, 70]). alignment_centers(16, [6, 26, 50, 74]). alignment_centers(17, [6, 30, 54, 78]). alignment_centers(18, [6, 30, 56, 82]). alignment_centers(19, [6, 30, 58, 86]). alignment_centers(20, [6, 34, 62, 90]). alignment_centers(21, [6, 28, 50, 72, 94]). alignment_centers(22, [6, 26, 50, 74, 98]). alignment_centers(23, [6, 30, 54, 78, 102]). alignment_centers(24, [6, 28, 54, 80, 106]). alignment_centers(25, [6, 32, 58, 84, 110]). alignment_centers(26, [6, 30, 58, 86, 114]). alignment_centers(27, [6, 34, 62, 90, 118]). alignment_centers(28, [6, 26, 50, 74, 98, 122]). alignment_centers(29, [6, 30, 54, 78, 102, 126]). alignment_centers(30, [6, 26, 52, 78, 104, 130]). alignment_centers(31, [6, 30, 56, 82, 108, 134]). alignment_centers(32, [6, 34, 60, 86, 112, 138]). alignment_centers(33, [6, 30, 58, 86, 114, 142]). alignment_centers(34, [6, 34, 62, 90, 118, 146]). alignment_centers(35, [6, 30, 54, 78, 102, 126, 150]). alignment_centers(36, [6, 24, 50, 76, 102, 128, 154]). alignment_centers(37, [6, 28, 54, 80, 106, 132, 158]). alignment_centers(38, [6, 32, 58, 84, 110, 136, 162]). alignment_centers(39, [6, 26, 54, 82, 110, 138, 166]). alignment_centers(40, [6, 30, 58, 86, 114, 142, 170]). rs_block_groups(1, l, [block_group(1, 26, 19)]). rs_block_groups(1, m, [block_group(1, 26, 16)]). rs_block_groups(1, q, [block_group(1, 26, 13)]). rs_block_groups(1, h, [block_group(1, 26, 9)]). rs_block_groups(2, l, [block_group(1, 44, 34)]). rs_block_groups(2, m, [block_group(1, 44, 28)]). rs_block_groups(2, q, [block_group(1, 44, 22)]). rs_block_groups(2, h, [block_group(1, 44, 16)]). rs_block_groups(3, l, [block_group(1, 70, 55)]). rs_block_groups(3, m, [block_group(1, 70, 44)]). rs_block_groups(3, q, [block_group(2, 35, 17)]). rs_block_groups(3, h, [block_group(2, 35, 13)]). rs_block_groups(4, l, [block_group(1, 100, 80)]). rs_block_groups(4, m, [block_group(2, 50, 32)]). rs_block_groups(4, q, [block_group(2, 50, 24)]). rs_block_groups(4, h, [block_group(4, 25, 9)]). rs_block_groups(5, l, [block_group(1, 134, 108)]). rs_block_groups(5, m, [block_group(2, 67, 43)]). rs_block_groups(5, q, [block_group(2, 33, 15), block_group(2, 34, 16)]). rs_block_groups(5, h, [block_group(2, 33, 11), block_group(2, 34, 12)]). rs_block_groups(6, l, [block_group(2, 86, 68)]). rs_block_groups(6, m, [block_group(4, 43, 27)]). rs_block_groups(6, q, [block_group(4, 43, 19)]). rs_block_groups(6, h, [block_group(4, 43, 15)]). rs_block_groups(7, l, [block_group(2, 98, 78)]). rs_block_groups(7, m, [block_group(4, 49, 31)]). rs_block_groups(7, q, [block_group(2, 32, 14), block_group(4, 33, 15)]). rs_block_groups(7, h, [block_group(4, 39, 13), block_group(1, 40, 14)]). rs_block_groups(8, l, [block_group(2, 121, 97)]). rs_block_groups(8, m, [block_group(2, 60, 38), block_group(2, 61, 39)]). rs_block_groups(8, q, [block_group(4, 40, 18), block_group(2, 41, 19)]). rs_block_groups(8, h, [block_group(4, 40, 14), block_group(2, 41, 15)]). rs_block_groups(9, l, [block_group(2, 146, 116)]). rs_block_groups(9, m, [block_group(3, 58, 36), block_group(2, 59, 37)]). rs_block_groups(9, q, [block_group(4, 36, 16), block_group(4, 37, 17)]). rs_block_groups(9, h, [block_group(4, 36, 12), block_group(4, 37, 13)]). rs_block_groups(10, l, [block_group(2, 86, 68), block_group(2, 87, 69)]). rs_block_groups(10, m, [block_group(4, 69, 43), block_group(1, 70, 44)]). rs_block_groups(10, q, [block_group(6, 43, 19), block_group(2, 44, 20)]). rs_block_groups(10, h, [block_group(6, 43, 15), block_group(2, 44, 16)]). rs_block_groups(11, l, [block_group(4, 101, 81)]). rs_block_groups(11, m, [block_group(1, 80, 50), block_group(4, 81, 51)]). rs_block_groups(11, q, [block_group(4, 50, 22), block_group(4, 51, 23)]). rs_block_groups(11, h, [block_group(3, 36, 12), block_group(8, 37, 13)]). rs_block_groups(12, l, [block_group(2, 116, 92), block_group(2, 117, 93)]). rs_block_groups(12, m, [block_group(6, 58, 36), block_group(2, 59, 37)]). rs_block_groups(12, q, [block_group(4, 46, 20), block_group(6, 47, 21)]). rs_block_groups(12, h, [block_group(7, 42, 14), block_group(4, 43, 15)]). rs_block_groups(13, l, [block_group(4, 133, 107)]). rs_block_groups(13, m, [block_group(8, 59, 37), block_group(1, 60, 38)]). rs_block_groups(13, q, [block_group(8, 44, 20), block_group(4, 45, 21)]). rs_block_groups(13, h, [block_group(12, 33, 11), block_group(4, 34, 12)]). rs_block_groups(14, l, [block_group(3, 145, 115), block_group(1, 146, 116)]). rs_block_groups(14, m, [block_group(4, 64, 40), block_group(5, 65, 41)]). rs_block_groups(14, q, [block_group(11, 36, 16), block_group(5, 37, 17)]). rs_block_groups(14, h, [block_group(11, 36, 12), block_group(5, 37, 13)]). rs_block_groups(15, l, [block_group(5, 109, 87), block_group(1, 110, 88)]). rs_block_groups(15, m, [block_group(5, 65, 41), block_group(5, 66, 42)]). rs_block_groups(15, q, [block_group(5, 54, 24), block_group(7, 55, 25)]). rs_block_groups(15, h, [block_group(11, 36, 12), block_group(7, 37, 13)]). rs_block_groups(16, l, [block_group(5, 122, 98), block_group(1, 123, 99)]). rs_block_groups(16, m, [block_group(7, 73, 45), block_group(3, 74, 46)]). rs_block_groups(16, q, [block_group(15, 43, 19), block_group(2, 44, 20)]). rs_block_groups(16, h, [block_group(3, 45, 15), block_group(13, 46, 16)]). rs_block_groups(17, l, [block_group(1, 135, 107), block_group(5, 136, 108)]). rs_block_groups(17, m, [block_group(10, 74, 46), block_group(1, 75, 47)]). rs_block_groups(17, q, [block_group(1, 50, 22), block_group(15, 51, 23)]). rs_block_groups(17, h, [block_group(2, 42, 14), block_group(17, 43, 15)]). rs_block_groups(18, l, [block_group(5, 150, 120), block_group(1, 151, 121)]). rs_block_groups(18, m, [block_group(9, 69, 43), block_group(4, 70, 44)]). rs_block_groups(18, q, [block_group(17, 50, 22), block_group(1, 51, 23)]). rs_block_groups(18, h, [block_group(2, 42, 14), block_group(19, 43, 15)]). rs_block_groups(19, l, [block_group(3, 141, 113), block_group(4, 142, 114)]). rs_block_groups(19, m, [block_group(3, 70, 44), block_group(11, 71, 45)]). rs_block_groups(19, q, [block_group(17, 47, 21), block_group(4, 48, 22)]). rs_block_groups(19, h, [block_group(9, 39, 13), block_group(16, 40, 14)]). rs_block_groups(20, l, [block_group(3, 135, 107), block_group(5, 136, 108)]). rs_block_groups(20, m, [block_group(3, 67, 41), block_group(13, 68, 42)]). rs_block_groups(20, q, [block_group(15, 54, 24), block_group(5, 55, 25)]). rs_block_groups(20, h, [block_group(15, 43, 15), block_group(10, 44, 16)]). rs_block_groups(21, l, [block_group(4, 144, 116), block_group(4, 145, 117)]). rs_block_groups(21, m, [block_group(17, 68, 42)]). rs_block_groups(21, q, [block_group(17, 50, 22), block_group(6, 51, 23)]). rs_block_groups(21, h, [block_group(19, 46, 16), block_group(6, 47, 17)]). rs_block_groups(22, l, [block_group(2, 139, 111), block_group(7, 140, 112)]). rs_block_groups(22, m, [block_group(17, 74, 46)]). rs_block_groups(22, q, [block_group(7, 54, 24), block_group(16, 55, 25)]). rs_block_groups(22, h, [block_group(34, 37, 13)]). rs_block_groups(23, l, [block_group(4, 151, 121), block_group(5, 152, 122)]). rs_block_groups(23, m, [block_group(4, 75, 47), block_group(14, 76, 48)]). rs_block_groups(23, q, [block_group(11, 54, 24), block_group(14, 55, 25)]). rs_block_groups(23, h, [block_group(16, 45, 15), block_group(14, 46, 16)]). rs_block_groups(24, l, [block_group(6, 147, 117), block_group(4, 148, 118)]). rs_block_groups(24, m, [block_group(6, 73, 45), block_group(14, 74, 46)]). rs_block_groups(24, q, [block_group(11, 54, 24), block_group(16, 55, 25)]). rs_block_groups(24, h, [block_group(30, 46, 16), block_group(2, 47, 17)]). rs_block_groups(25, l, [block_group(8, 132, 106), block_group(4, 133, 107)]). rs_block_groups(25, m, [block_group(8, 75, 47), block_group(13, 76, 48)]). rs_block_groups(25, q, [block_group(7, 54, 24), block_group(22, 55, 25)]). rs_block_groups(25, h, [block_group(22, 45, 15), block_group(13, 46, 16)]). rs_block_groups(26, l, [block_group(10, 142, 114), block_group(2, 143, 115)]). rs_block_groups(26, m, [block_group(19, 74, 46), block_group(4, 75, 47)]). rs_block_groups(26, q, [block_group(28, 50, 22), block_group(6, 51, 23)]). rs_block_groups(26, h, [block_group(33, 46, 16), block_group(4, 47, 17)]). rs_block_groups(27, l, [block_group(8, 152, 122), block_group(4, 153, 123)]). rs_block_groups(27, m, [block_group(22, 73, 45), block_group(3, 74, 46)]). rs_block_groups(27, q, [block_group(8, 53, 23), block_group(26, 54, 24)]). rs_block_groups(27, h, [block_group(12, 45, 15), block_group(28, 46, 16)]). rs_block_groups(28, l, [block_group(3, 147, 117), block_group(10, 148, 118)]). rs_block_groups(28, m, [block_group(3, 73, 45), block_group(23, 74, 46)]). rs_block_groups(28, q, [block_group(4, 54, 24), block_group(31, 55, 25)]). rs_block_groups(28, h, [block_group(11, 45, 15), block_group(31, 46, 16)]). rs_block_groups(29, l, [block_group(7, 146, 116), block_group(7, 147, 117)]). rs_block_groups(29, m, [block_group(21, 73, 45), block_group(7, 74, 46)]). rs_block_groups(29, q, [block_group(1, 53, 23), block_group(37, 54, 24)]). rs_block_groups(29, h, [block_group(19, 45, 15), block_group(26, 46, 16)]). rs_block_groups(30, l, [block_group(5, 145, 115), block_group(10, 146, 116)]). rs_block_groups(30, m, [block_group(19, 75, 47), block_group(10, 76, 48)]). rs_block_groups(30, q, [block_group(15, 54, 24), block_group(25, 55, 25)]). rs_block_groups(30, h, [block_group(23, 45, 15), block_group(25, 46, 16)]). rs_block_groups(31, l, [block_group(13, 145, 115), block_group(3, 146, 116)]). rs_block_groups(31, m, [block_group(2, 74, 46), block_group(29, 75, 47)]). rs_block_groups(31, q, [block_group(42, 54, 24), block_group(1, 55, 25)]). rs_block_groups(31, h, [block_group(23, 45, 15), block_group(28, 46, 16)]). rs_block_groups(32, l, [block_group(17, 145, 115)]). rs_block_groups(32, m, [block_group(10, 74, 46), block_group(23, 75, 47)]). rs_block_groups(32, q, [block_group(10, 54, 24), block_group(35, 55, 25)]). rs_block_groups(32, h, [block_group(19, 45, 15), block_group(35, 46, 16)]). rs_block_groups(33, l, [block_group(17, 145, 115), block_group(1, 146, 116)]). rs_block_groups(33, m, [block_group(14, 74, 46), block_group(21, 75, 47)]). rs_block_groups(33, q, [block_group(29, 54, 24), block_group(19, 55, 25)]). rs_block_groups(33, h, [block_group(11, 45, 15), block_group(46, 46, 16)]). rs_block_groups(34, l, [block_group(13, 145, 115), block_group(6, 146, 116)]). rs_block_groups(34, m, [block_group(14, 74, 46), block_group(23, 75, 47)]). rs_block_groups(34, q, [block_group(44, 54, 24), block_group(7, 55, 25)]). rs_block_groups(34, h, [block_group(59, 46, 16), block_group(1, 47, 17)]). rs_block_groups(35, l, [block_group(12, 151, 121), block_group(7, 152, 122)]). rs_block_groups(35, m, [block_group(12, 75, 47), block_group(26, 76, 48)]). rs_block_groups(35, q, [block_group(39, 54, 24), block_group(14, 55, 25)]). rs_block_groups(35, h, [block_group(22, 45, 15), block_group(41, 46, 16)]). rs_block_groups(36, l, [block_group(6, 151, 121), block_group(14, 152, 122)]). rs_block_groups(36, m, [block_group(6, 75, 47), block_group(34, 76, 48)]). rs_block_groups(36, q, [block_group(46, 54, 24), block_group(10, 55, 25)]). rs_block_groups(36, h, [block_group(2, 45, 15), block_group(64, 46, 16)]). rs_block_groups(37, l, [block_group(17, 152, 122), block_group(4, 153, 123)]). rs_block_groups(37, m, [block_group(29, 74, 46), block_group(14, 75, 47)]). rs_block_groups(37, q, [block_group(49, 54, 24), block_group(10, 55, 25)]). rs_block_groups(37, h, [block_group(24, 45, 15), block_group(46, 46, 16)]). rs_block_groups(38, l, [block_group(4, 152, 122), block_group(18, 153, 123)]). rs_block_groups(38, m, [block_group(13, 74, 46), block_group(32, 75, 47)]). rs_block_groups(38, q, [block_group(48, 54, 24), block_group(14, 55, 25)]). rs_block_groups(38, h, [block_group(42, 45, 15), block_group(32, 46, 16)]). rs_block_groups(39, l, [block_group(20, 147, 117), block_group(4, 148, 118)]). rs_block_groups(39, m, [block_group(40, 75, 47), block_group(7, 76, 48)]). rs_block_groups(39, q, [block_group(43, 54, 24), block_group(22, 55, 25)]). rs_block_groups(39, h, [block_group(10, 45, 15), block_group(67, 46, 16)]). rs_block_groups(40, l, [block_group(19, 148, 118), block_group(6, 149, 119)]). rs_block_groups(40, m, [block_group(18, 75, 47), block_group(31, 76, 48)]). rs_block_groups(40, q, [block_group(34, 54, 24), block_group(34, 55, 25)]). rs_block_groups(40, h, [block_group(20, 45, 15), block_group(61, 46, 16)]). %% Tests % % The tests are written as executable examples. They cover ordinary round % trips, explicit segment streams, damaged grids, erasures, and mixed % erasure/error recovery. %% test is det. % % Run the self-check suite. test :- test_pad_word, test_round_trip("BYAKUREN", [version(1), level(q), mode(alphanumeric), mask(3)]), test_round_trip("1234567890", [version(1), level(h), mode(numeric), mask(7)]), test_round_trip("byakuren", [version(1), level(m), mode(byte), mask(0)]), test_round_trip("THIS IS A LONGER QR EXAMPLE FOR VERSION FOUR", [version(4), level(m), mode(byte), mask(2)]), test_round_trip("VERSION SEVEN REFERENCE CHECK 1234567890", [version(7), level(q), mode(byte), mask(5)]), test_round_trip("1234567890123456789012345678901234567890", [version(10), level(h), mode(numeric), mask(6)]), test_round_trip("lambda λ", [version(2), level(h), mode(utf8), mask(0)]), test_round_trip("漢字", [version(1), level(h), mode(kanji), mask(0)]), test_data_round_trip(qr_data([fnc1(first), alphanumeric([65,29,66])]), [version(1), level(h), mode(segments), mask(0)]), test_data_round_trip(qr_data([structured_append(1,3,170), numeric("123")]), [version(1), level(h), mode(segments), mask(0)]), test_variant("1234", [version(1), level(h), mode(numeric), mask(0)]), test_variant("1234", [version(1), level(q), mode(alphanumeric), mask(7)]), test_variant("byakuren", [version(1), level(l), mode(byte), mask(3)]), test_corrupted_grid_recovery("byakuren", [version(1), level(q), mode(byte), mask(0)]), test_erasure_grid_recovery("byakuren", [version(1), level(q), mode(byte), mask(0)]), test_mixed_grid_recovery("byakuren", [version(1), level(q), mode(byte), mask(0)]), test_variable_erasure_fill("byakuren", [version(1), level(q), mode(byte), mask(0)]), test_fixed_spec_data_words("byakuren", [version(1), level(q), mode(byte), mask(0)], [64,134,39,150,22,183,87,38,86,224,236,17,236]), test_spec_list_output, test_spec_constraints, test_spec_counts, test_text_qr_decode_half, test_text_qr_decode_wide, test_text_qr_decode_full, test_text_qr_decode_inverted, test_text_qr_decode_file, test_text_qr_decode_unique, test_eci_plain_text_output, test_eci_segment_output, test_unknown_eci_segment_output, test_penalty_analysis, test_mask_penalties_analysis, test_codewords_analysis, test_analysis_bundle, test_analysis_backtracking, test_capacity_analysis, test_geometry_analysis, test_sequence_parity_analysis, test_sequence_single_symbol, test_sequence_symbol_best_mask, test_sequence_manual_decode_text, test_sequence_manual_decode_items, test_property_text_round_trips, test_property_best_penalties, test_property_recovery_corpus, test_property_eci_data_round_trips, test_auto_version("THIS MESSAGE FORCES A HIGHER VERSION QR CODE", 4), test_auto_version("this lowercase payload forces a larger byte mode qr code", 6), write('qr.pl tests passed'), nl, !. test_pad_word :- findall(Word0, pad_word(0, Word0), [236]), findall(Word1, pad_word(1, Word1), [17]). test_round_trip(Text, Spec) :- qr_code(Text, Grid, Spec, _Stages), qr_code(RoundTripText, Grid, RoundTripSpec, _RoundTripStages), text_codes(Text, Codes), text_codes(RoundTripText, RoundTripCodes), RoundTripCodes = Codes, RoundTripSpec = Spec. test_data_round_trip(Data, Spec) :- qr_code(Data, Grid, Spec, _Stages), qr_code(RoundTripData, Grid, RoundTripSpec, _RoundTripStages), normalized_test_data(Data, NormalizedData), normalized_test_data(RoundTripData, NormalizedRoundTripData), NormalizedRoundTripData = NormalizedData, RoundTripSpec = Spec. test_variant(Text, Spec) :- qr_code(Text, _Grid, Spec, _Stages). test_corrupted_grid_recovery(Text, Spec) :- qr_code(Text, Grid, Spec, _Stages), flip_first_data_module(Grid, Spec, DamagedGrid), qr_code(RoundTripText, DamagedGrid, RoundTripSpec, DamageStages), text_codes(Text, Codes), text_codes(RoundTripText, RoundTripCodes), RoundTripCodes = Codes, RoundTripSpec = Spec, member(stage(rs_corrections, Corrections), DamageStages), corrected_block_present(Corrections). test_erasure_grid_recovery(Text, Spec) :- qr_code(Text, Grid, Spec, _Stages), erase_first_data_module(Grid, Spec, PartialGrid), qr_code(RoundTripText, PartialGrid, RoundTripSpec, DecodeStages), text_codes(Text, Codes), text_codes(RoundTripText, RoundTripCodes), RoundTripCodes = Codes, RoundTripSpec = Spec, member(stage(extracted_codewords, ExtractedCodewords), DecodeStages), member(erasure, ExtractedCodewords), member(stage(rs_corrections, Corrections), DecodeStages), corrected_block_present(Corrections). test_mixed_grid_recovery(Text, Spec) :- qr_code(Text, Grid, Spec, _Stages), erase_data_module(Grid, Spec, 0, PartialGrid0), flip_data_module(PartialGrid0, Spec, 8, PartialGrid), qr_code(RoundTripText, PartialGrid, RoundTripSpec, DecodeStages), text_codes(Text, Codes), text_codes(RoundTripText, RoundTripCodes), RoundTripCodes = Codes, RoundTripSpec = Spec, member(stage(rs_corrections, Corrections), DecodeStages), corrected_block_present(Corrections). test_variable_erasure_fill(Text, Spec) :- qr_code(Text, Grid, Spec, _Stages), unknown_first_data_module(Grid, Spec, PartialGrid, Cell), qr_code(RoundTripText, PartialGrid, RoundTripSpec, DecodeStages), text_codes(Text, Codes), text_codes(RoundTripText, RoundTripCodes), RoundTripCodes = Codes, RoundTripSpec = Spec, binary_bit(Cell), member(stage(rs_corrections, Corrections), DecodeStages), corrected_block_present(Corrections). test_fixed_spec_data_words(Text, Spec, ExpectedDataWords) :- findall(DataWords, ( qr_code(Text, _Grid, Spec, Stages), member(stage(data_codewords, DataWords), Stages) ), [ExpectedDataWords]). test_spec_list_output :- qr_code("byakuren", _Grid, Spec, _Stages), Spec = [version(_), level(_), mode(_), mask(_)], member(version(1), Spec). test_spec_constraints :- qr_spec(Spec1), member(version(1), Spec1), qr_code("byakuren", _Grid1, Spec1, _Stages1), spec_property(level(h), Spec2), qr_code("byakuren", _Grid2, Spec2, _Stages2), spec_property(mask(0), Spec3), qr_code("byakuren", _Grid3, Spec3, _Stages3). test_spec_counts :- test_solution_count((spec_version(Spec0, 1), qr_code("byakuren", _Grid0, Spec0, _Stages0)), 48), test_solution_count((qr_spec(Spec1), member(version(1), Spec1), qr_code("byakuren", _Grid1, Spec1, _Stages1)), 48), test_solution_count((spec_version(Spec2, 1), spec_level(Spec2, q), qr_code("byakuren", _Grid2, Spec2, _Stages2)), 16), test_solution_count((spec_version(Spec3, 1), spec_mode(Spec3, byte), qr_code("byakuren", _Grid3, Spec3, _Stages3)), 24), test_solution_count((spec_version(Spec4, 1), spec_mode(Spec4, utf8), qr_code("byakuren", _Grid4, Spec4, _Stages4)), 24), test_solution_count((spec_version(Spec5, 1), spec_mask(Spec5, 0), qr_code("byakuren", _Grid5, Spec5, _Stages5)), 6), test_best_qr_solution, test_best_qr_segments. test_best_qr_solution :- findall(Spec, qr:qr_solution("byakuren", Spec, _Grid), [[version(1), level(q), mode(byte), mask(7)]]). test_best_qr_segments :- findall(Spec, qr:qr_solution("A1漢B2", Spec, _Grid), [[version(1), level(q), mode(segments), mask(6)]]). test_sequence_single_symbol :- qr_solution("byakuren", Spec, Grid), qr_sequence("byakuren", [SequenceGrid], [SequenceSpec], SequenceStages), SequenceGrid = Grid, SequenceSpec = Spec, member(stage(sequence_total, 1), SequenceStages). % Focused regression for mixed-segment single-symbol orchestration. test_sequence_single_symbol_segments :- qr_solution("A1漢B2", Spec, Grid), qr_sequence("A1漢B2", [SequenceGrid], [SequenceSpec], SequenceStages), SequenceGrid = Grid, SequenceSpec = Spec, member(stage(sequence_total, 1), SequenceStages). test_sequence_manual_decode_text :- Text = "byakuren", qr_sequence_parity(Text, Parity), qr_code(qr_data([structured_append(0,1,Parity), byte("bya")]), Grid0, Spec0, _Stages0), qr_code(qr_data([structured_append(1,1,Parity), byte("kuren")]), Grid1, Spec1, _Stages1), qr_sequence(RoundTripText, [Grid1, Grid0], Specs, SequenceStages), text_codes(Text, Codes), text_codes(RoundTripText, RoundTripCodes), RoundTripCodes = Codes, Specs = [Spec0, Spec1], member(stage(sequence_total, 2), SequenceStages), member(stage(sequence_parity, Parity), SequenceStages). test_sequence_manual_decode_items :- Data = qr_data([fnc1(first), byte("bya"), byte("kuren")]), qr_sequence_parity(Data, Parity), qr_code(qr_data([structured_append(0,1,Parity), fnc1(first), byte("bya")]), Grid0, Spec0, _Stages0), qr_code(qr_data([structured_append(1,1,Parity), byte("kuren")]), Grid1, Spec1, _Stages1), qr_sequence(RoundTripData, [Grid1, Grid0], RoundTripSpecs), normalized_test_data(Data, NormalizedData), normalized_test_data(RoundTripData, NormalizedRoundTripData), NormalizedRoundTripData = NormalizedData, RoundTripSpecs = [Spec0, Spec1]. test_solution_count(Goal, ExpectedCount) :- findall(true, Goal, Solutions), length(Solutions, ExpectedCount). test_text_qr_decode_half :- Spec = [version(1), level(q), mode(byte), mask(0)], qr_code("byakuren", Grid, Spec, _Stages), qr_render_lines(Grid, Lines0), pad_text_qr_lines(Lines0, 1, 2, 3, 4, PaddedLines), ansi_wrap_lines(PaddedLines, WrappedLines), lines_text(WrappedLines, Text), qr_decode(Text, Data, DecodedSpec), text_codes(Data, DataCodes), text_codes("byakuren", ExpectedCodes), DataCodes = ExpectedCodes, DecodedSpec = Spec. test_text_qr_decode_wide :- Spec = [version(1), level(q), mode(byte), mask(0)], qr_code("byakuren", Grid, Spec, _Stages), qr_render_lines_wide(Grid, Lines0), pad_text_qr_lines(Lines0, 2, 1, 4, 3, PaddedLines), qr_decode(PaddedLines, Data, DecodedSpec), text_codes(Data, DataCodes), text_codes("byakuren", ExpectedCodes), DataCodes = ExpectedCodes, DecodedSpec = Spec. test_text_qr_decode_full :- Spec = [version(1), level(q), mode(byte), mask(0)], qr_code("byakuren", Grid, Spec, _Stages), qr_render_lines_full(Grid, Lines0), pad_text_qr_lines(Lines0, 1, 1, 2, 2, PaddedLines), qr_decode(PaddedLines, Data), text_codes(Data, DataCodes), text_codes("byakuren", ExpectedCodes), DataCodes = ExpectedCodes. test_text_qr_decode_inverted :- Spec = [version(1), level(q), mode(byte), mask(0)], qr_code("byakuren", Grid, Spec, _Stages), quiet_zone_grid(Grid, QuietGrid), invert_binary_grid(QuietGrid, InvertedGrid), maplist(render_full_text_row, InvertedGrid, Lines), qr_decode(Lines, Data, DecodedSpec), text_codes(Data, DataCodes), text_codes("byakuren", ExpectedCodes), DataCodes = ExpectedCodes, DecodedSpec = Spec. test_text_qr_decode_file :- Spec = [version(1), level(q), mode(byte), mask(0)], qr_code("byakuren", Grid, Spec, _Stages), qr_render_lines(Grid, Lines), lines_codes(Lines, Codes), TestPath = "/tmp/qr-text-decode-test.txt", write_codes_file(TestPath, Codes), qr_decode_file(TestPath, Data, DecodedSpec), text_codes(Data, DataCodes), text_codes("byakuren", ExpectedCodes), DataCodes = ExpectedCodes, DecodedSpec = Spec. test_text_qr_decode_unique :- test_solution_count(test_text_qr_decode_half, 1), test_solution_count(test_text_qr_decode_wide, 1), test_solution_count(test_text_qr_decode_full, 1), test_solution_count(test_text_qr_decode_inverted, 1), test_solution_count(test_text_qr_decode_file, 1). test_eci_plain_text_output :- test_eci_text_round_trip(ascii("ASCII ONLY"), "ASCII ONLY"), test_eci_text_round_trip(utf16be("lambda λ"), "lambda λ"), test_eci_text_round_trip(eci_text(27, "ASCII ONLY"), "ASCII ONLY"), test_eci_text_round_trip(eci_text(25, "lambda λ"), "lambda λ"). test_eci_text_round_trip(Item, Text) :- qr_code(qr_data([Item]), Grid, Spec, _Stages), qr_code(RoundTripText, Grid, Spec, _RoundTripStages), text_codes(Text, Codes), text_codes(RoundTripText, RoundTripCodes), RoundTripCodes = Codes. test_eci_segment_output :- test_data_round_trip(qr_data([fnc1(first), ascii("ASCII ONLY")]), _Spec), test_data_round_trip(qr_data([fnc1(first), utf16be("lambda λ")]), _Spec). test_unknown_eci_segment_output :- Data = qr_data([fnc1(first), eci(899), byte([65,66])]), qr_code(Data, Grid, Spec, _Stages), qr_code(RoundTripData, Grid, Spec, _RoundTripStages), normalized_test_data(Data, NormalizedData), normalized_test_data(RoundTripData, NormalizedRoundTripData), NormalizedRoundTripData = NormalizedData. test_penalty_analysis :- Spec = [version(1), level(q), mode(byte), mask(0)], qr_code("byakuren", Grid, Spec, _Stages), qr_penalty(Grid, Penalty), qr_penalty_breakdown(Grid, Breakdown), member(runs(_RunPenalty), Breakdown), member(blocks(_BlockPenalty), Breakdown), member(finders(_FinderPenalty), Breakdown), member(balance(_BalancePenalty), Breakdown), member(total(Penalty), Breakdown). test_mask_penalties_analysis :- Spec = [version(1), level(q), mode(byte), mask(_Mask)], qr_mask_penalties("byakuren", Spec, MaskPenalties), length(MaskPenalties, 8), member(mask_penalty(7, Penalty7), MaskPenalties), best_mask_penalty(MaskPenalties, 7, Penalty7), qr_mask_penalties("byakuren", [version(1), level(q), mode(byte), mask(3)], [mask_penalty(3, _Penalty3)]). test_codewords_analysis :- Spec = [version(1), level(q), mode(byte), mask(0)], qr_code("byakuren", Grid, Spec, EncodeStages), member(stage(codewords, Codewords), EncodeStages), qr_codewords("byakuren", Spec, ReceivedCodewords0, Codewords0), ReceivedCodewords0 = Codewords0, Codewords0 = Codewords, flip_first_data_module(Grid, Spec, DamagedGrid), qr_codewords(DamagedGrid, Spec, ReceivedCodewords1, CorrectedCodewords1), ReceivedCodewords1 \= CorrectedCodewords1, CorrectedCodewords1 = Codewords. test_analysis_bundle :- qr_analysis("byakuren", Analysis0), member(spec(Spec0), Analysis0), member(grid(Grid0), Analysis0), member(capacity(Capacity0), Analysis0), member(penalty(Penalty0), Analysis0), member(penalty_breakdown(Breakdown0), Analysis0), member(received_codewords(Codewords0), Analysis0), member(codewords(Codewords0), Analysis0), member(mask_penalties(MaskPenalties0), Analysis0), member(total(Penalty0), Breakdown0), member(size(21), Capacity0), length(MaskPenalties0, 8), flip_first_data_module(Grid0, Spec0, DamagedGrid), qr_analysis(DamagedGrid, Analysis1), member(data(Data1), Analysis1), text_codes(Data1, DataCodes1), text_codes("byakuren", ExpectedCodes1), DataCodes1 = ExpectedCodes1, member(received_codewords(Received1), Analysis1), member(codewords(Corrected1), Analysis1), Received1 \= Corrected1. test_analysis_backtracking :- analysis_has_spec("1234", 1, h, numeric, 0), analysis_has_spec("1234", 1, h, numeric, 1), qr_mask_penalties("1234", [version(1), level(h), mode(numeric), mask(0)], [mask_penalty(0, _Penalty0)]), qr_mask_penalties("1234", [version(1), level(q), mode(numeric), mask(0)], [mask_penalty(0, _Penalty1)]). analysis_has_spec(Text, Version, Level, Mode, Mask) :- qr_analysis(Text, Analysis), member(spec(Spec), Analysis), spec_version(Spec, Version), spec_level(Spec, Level), spec_mode(Spec, Mode), spec_mask(Spec, Mask). test_capacity_analysis :- qr_capacity([version(1), level(q), mode(_Mode), mask(_Mask)], Capacity), member(size(21), Capacity), member(total_codewords(26), Capacity), member(data_codewords(13), Capacity), member(data_bits(104), Capacity), member(ecc_codewords(13), Capacity), test_solution_count(qr_capacity(_Spec, _AnyCapacity), 160), test_solution_count((spec_version(Spec0, 1), qr_capacity(Spec0, _Capacity0)), 4), test_solution_count((qr_spec(Spec1), member(version(1), Spec1), qr_capacity(Spec1, _Capacity1)), 4). test_geometry_analysis :- qr_version_size(7, 45), qr_code("byakuren", Grid, [version(1), level(q), mode(byte), mask(0)], _Stages), qr_grid_size(Grid, 21), qr_grid_version(Grid, 1). test_sequence_parity_analysis :- qr_sequence_parity("byakuren", 29), qr_sequence_parity(qr_data([fnc1(first), byte("bya"), byte("kuren")]), 29). test_sequence_symbol_best_mask :- qr_sequence_parity("byakuren", Parity), normalize_qr_items([byte("byakuren")], PayloadItems), sequence_symbol_data(0, 1, Parity, PayloadItems, SymbolData), sequence_symbol_items(0, 1, Parity, PayloadItems, SymbolItems), best_symbol_for_items(SymbolItems, 1, 40, Spec, Grid), spec_version(Spec, Version), spec_level(Spec, Level), spec_mode(Spec, Mode), spec_mask(Spec, Mask), qr_mask_penalties(SymbolData, [version(Version), level(Level), mode(Mode), mask(_Mask)], MaskPenalties), best_mask_penalty(MaskPenalties, Mask, Penalty), qr_penalty(Grid, Penalty). test_property_text_round_trips :- property_text_corpus(Texts), property_text_round_trips(Texts). property_text_round_trips([]). property_text_round_trips([Text|Texts]) :- qr_solution(Text, Spec, Grid), qr_code(RoundTripText, Grid, Spec, _Stages), text_codes(Text, Codes), text_codes(RoundTripText, RoundTripCodes), RoundTripCodes = Codes, qr_analysis(Text, _Analysis), property_text_round_trips(Texts). test_property_best_penalties :- property_text_corpus(Texts), property_best_penalties(Texts). property_best_penalties([]). property_best_penalties([Text|Texts]) :- qr_solution(Text, Spec, Grid), spec_version(Spec, Version), spec_level(Spec, Level), spec_mode(Spec, Mode), spec_mask(Spec, Mask), qr_mask_penalties(Text, [version(Version), level(Level), mode(Mode), mask(_Mask)], MaskPenalties), best_mask_penalty(MaskPenalties, Mask, Penalty), qr_penalty(Grid, Penalty), property_best_penalties(Texts). test_property_recovery_corpus :- property_recovery_texts(Texts), property_recovery_corpus(Texts). property_recovery_corpus([]). property_recovery_corpus([Text|Texts]) :- qr_solution(Text, Spec, Grid), flip_first_data_module(Grid, Spec, DamagedGrid), qr_code(RoundTripText0, DamagedGrid, Spec, _DamageStages), text_codes(Text, Codes), text_codes(RoundTripText0, RoundTripCodes0), RoundTripCodes0 = Codes, erase_first_data_module(Grid, Spec, PartialGrid), qr_code(RoundTripText1, PartialGrid, Spec, _PartialStages), text_codes(RoundTripText1, RoundTripCodes1), RoundTripCodes1 = Codes, property_recovery_corpus(Texts). test_property_eci_data_round_trips :- property_eci_data_corpus(DataItems), property_eci_data_round_trips(DataItems). property_eci_data_round_trips([]). property_eci_data_round_trips([Data|DataItems]) :- qr_solution(Data, Spec, Grid), qr_code(RoundTripData, Grid, Spec, _Stages), normalized_test_data(Data, NormalizedData), normalized_test_data(RoundTripData, NormalizedRoundTripData), NormalizedRoundTripData = NormalizedData, property_eci_data_round_trips(DataItems). property_text_corpus(["1234567890", "BYAKUREN", "byakuren", "lambda λ", "漢字"]). property_recovery_texts(["1234567890", "byakuren", "漢字"]). property_eci_data_corpus([qr_data([fnc1(first), ascii("ASCII ONLY")]), qr_data([fnc1(first), eci_text(27, "ASCII ONLY")]), qr_data([fnc1(first), utf16be("lambda λ")])]). best_mask_penalty([mask_penalty(Mask, Penalty)|MaskPenalties], BestMask, BestPenalty) :- best_mask_penalty(MaskPenalties, Mask, Penalty, BestMask, BestPenalty). best_mask_penalty([], BestMask, BestPenalty, BestMask, BestPenalty). best_mask_penalty([mask_penalty(Mask, Penalty)|MaskPenalties], Mask0, Penalty0, BestMask, BestPenalty) :- ( key(Penalty, Mask) @< key(Penalty0, Mask0) -> best_mask_penalty(MaskPenalties, Mask, Penalty, BestMask, BestPenalty) ; best_mask_penalty(MaskPenalties, Mask0, Penalty0, BestMask, BestPenalty) ). pad_text_qr_lines(Lines0, TopCount, BottomCount, LeftCount, RightCount, Lines) :- spaces(LeftCount, LeftPadding), spaces(RightCount, RightPadding), maplist(pad_text_qr_line(LeftPadding, RightPadding), Lines0, MiddleLines), max_text_line_width(MiddleLines, Width), spaces(Width, BlankLine), repeat_text_line(TopCount, BlankLine, TopLines), repeat_text_line(BottomCount, BlankLine, BottomLines), append(TopLines, MiddleLines, Lines1), append(Lines1, BottomLines, Lines). pad_text_qr_line(LeftPadding, RightPadding, Line0, Line) :- append(LeftPadding, Line0, Line1), append(Line1, RightPadding, Line). repeat_text_line(0, _Line, []). repeat_text_line(Count, Line, [Line|Lines]) :- Count > 0, Count1 is Count - 1, repeat_text_line(Count1, Line, Lines). ansi_wrap_lines([], []). ansi_wrap_lines([Line|Lines], [WrappedLine|WrappedLines]) :- ansi_wrap_line(Line, WrappedLine), ansi_wrap_lines(Lines, WrappedLines). ansi_wrap_line(Line, WrappedLine) :- append([27,91,55,109], Line, Line1), append(Line1, [27,91,48,109], WrappedLine). lines_text(Lines, Text) :- lines_codes(Lines, Codes), codes_text(Codes, Text). lines_codes([], []). lines_codes([Line], Line). lines_codes([Line,NextLine|Lines], Codes) :- lines_codes([NextLine|Lines], RestCodes), append(Line, [10|RestCodes], Codes). write_codes_file(Path, Codes) :- open(Path, write, Stream), write_stream_codes(Stream, Codes), close(Stream). write_stream_codes(_Stream, []). write_stream_codes(Stream, [Code|Codes]) :- put_code(Stream, Code), write_stream_codes(Stream, Codes). qr_render_lines_full(Grid, Lines) :- quiet_zone_grid(Grid, QuietGrid), maplist(render_full_text_row, QuietGrid, Lines). render_full_text_row([], []). render_full_text_row([1|Bits], [9608|Codes]) :- render_full_text_row(Bits, Codes). render_full_text_row([0|Bits], [32|Codes]) :- render_full_text_row(Bits, Codes). repeat_code_text(Count, Code, Text) :- repeat_code_list(Count, Code, Codes), codes_text(Codes, Text). repeat_code_list(0, _Code, []). repeat_code_list(Count, Code, [Code|Codes]) :- Count > 0, Count1 is Count - 1, repeat_code_list(Count1, Code, Codes). test_auto_version(Text, ExpectedVersion) :- qr_code(Text, _Grid, [version(ExpectedVersion), level(_Level), mode(_Mode), mask(0)], _Stages). normalized_test_data(qr_data(RawItems), qr_data(Items)) :- normalize_qr_items(RawItems, NormalizedItems), denormalize_qr_items(NormalizedItems, Items). normalized_test_data(Text, Text). flip_first_data_module(Grid, Spec, DamagedGrid) :- flip_data_module(Grid, Spec, 0, DamagedGrid). erase_first_data_module(Grid, Spec, PartialGrid) :- erase_data_module(Grid, Spec, 0, PartialGrid). unknown_first_data_module(Grid, Spec, PartialGrid, Cell) :- spec_version(Spec, Version), data_module_position(Version, 0, Row, Col), set_grid_bit(Grid, Row, Col, Cell, PartialGrid). erase_data_module(Grid, Spec, Index, PartialGrid) :- spec_version(Spec, Version), data_module_position(Version, Index, Row, Col), set_grid_bit(Grid, Row, Col, u, PartialGrid). flip_data_module(Grid, Spec, Index, DamagedGrid) :- spec_version(Spec, Version), data_module_position(Version, Index, Row, Col), flip_grid_bit(Grid, Row, Col, DamagedGrid). % Convenience wrappers around spec_property/2 for the four spec fields. These % are useful when you want a more predicate-style interface than property terms. % % Examples: % ?- spec_version(Spec, 1), qr("byakuren", Spec). % ?- spec_mask(Spec, 0), qr("byakuren", Spec, Grid). % ?- spec_level(Spec, h), spec_mode(Spec, byte), qr("byakuren", Spec, Grid). %% spec_version(?Spec, ?Version) is semidet. %% spec_level(?Spec, ?Level) is semidet. %% spec_mode(?Spec, ?Mode) is semidet. %% spec_mask(?Spec, ?Mask) is semidet. % % Convenience wrappers around spec_property/2 for the four spec fields. spec_version(Spec, Version) :- spec_property(version(Version), Spec). spec_level(Spec, Level) :- spec_property(level(Level), Spec). spec_mode(Spec, Mode) :- spec_property(mode(Mode), Spec). spec_mask(Spec, Mask) :- spec_property(mask(Mask), Spec). data_module_position(Version, Index, Row, Col) :- template_board(Version, FunctionBoard), data_positions(FunctionBoard, Positions), nth0(Index, Positions, cell_at(Row, Col, data, _)). flip_grid_bit(Grid0, Row, Col, Grid) :- nth0(Row, Grid0, GridRow0), nth0(Col, GridRow0, Bit0), bit_flip(Bit0, Bit), set_list_nth0(GridRow0, Col, Bit, GridRow), set_list_nth0(Grid0, Row, GridRow, Grid). set_grid_bit(Grid0, Row, Col, Bit, Grid) :- nth0(Row, Grid0, GridRow0), set_list_nth0(GridRow0, Col, Bit, GridRow), set_list_nth0(Grid0, Row, GridRow, Grid). set_list_nth0([_Value0|Values], 0, Value, [Value|Values]). set_list_nth0([Value0|Values0], Index, Value, [Value0|Values]) :- Index > 0, Index1 is Index - 1, set_list_nth0(Values0, Index1, Value, Values). corrected_block_present([rs_corrected(_)|_]). corrected_block_present([rs_ok|Corrections]) :- corrected_block_present(Corrections).