← All repositories

crossmate

A collaborative crossword app for iPhone and iPad

git clone https://code.inqk.net/crossmate.git


Crossmate/Services/GridSilhouette.swift (6558B)

1import Foundation
2
3/// Encodes a crossword's block layout — its grid "silhouette" — into a compact,
4/// URL-safe path segment for a share link, and back. The segment lets the link
5/// worker render a preview of the actual grid (and, later, lets the app paint a
6/// placeholder the instant a link is tapped) without any CloudKit round-trip.
7///
8/// Wire format: `<tag><size…><payload>`
9/// - `tag`     case selects geometry and symmetry. Lowercase `s`/`f` are square
10///             grids carrying a single side digit; uppercase `S`/`F` are
11///             rectangular grids carrying a width digit then a height digit.
12///             `s`/`S` mean the grid is 180°-rotationally symmetric (only the
13///             first ⌈N/2⌉ cells are stored, since the rest mirror them); `f`/`F`
14///             are a full dump of every cell.
15/// - `size…`   each dimension as a single base-36 digit (`f` = 15, `l` = 21), so
16///             sides are bounded to 2…35.
17/// - `payload` the cell bits, row-major, MSB-first, `1` = block, as base64url
18///             without padding. Each character therefore carries six cells.
19///
20/// A symmetric 15×15 lands in ~22 characters (`s` `f` + 20); the full fallback
21/// for an asymmetric 15×15 is ~40. The 180° mirror partner of cell `k` in a
22/// `w×h` grid is `n-1-k` regardless of the dimensions, so the symmetric packing
23/// and the rectangular case share the same reconstruction. See
24/// `GridSilhouetteTests`.
25enum GridSilhouette {
26    static let minSide = 2
27    /// A single base-36 size digit tops out at 35.
28    static let maxSide = 35
29
30    struct Grid: Equatable {
31        let width: Int
32        let height: Int
33        /// Row-major, `true` = block.
34        let blocks: [Bool]
35
36        init(width: Int, height: Int, blocks: [Bool]) {
37            self.width = width
38            self.height = height
39            self.blocks = blocks
40        }
41
42        /// Convenience for the common square case.
43        init(side: Int, blocks: [Bool]) {
44            self.init(width: side, height: side, blocks: blocks)
45        }
46    }
47
48    /// Encodes a square grid, or `nil` when the side falls outside
49    /// `minSide...maxSide` or the block count doesn't match. A thin shim over
50    /// `encode(width:height:blocks:)` for the square call sites and tests.
51    static func encode(side: Int, blocks: [Bool]) -> String? {
52        encode(width: side, height: side, blocks: blocks)
53    }
54
55    /// Encodes a grid, or `nil` when either dimension falls outside
56    /// `minSide...maxSide` or `blocks` doesn't hold exactly `width * height`
57    /// cells. A square grid uses the compact lowercase single-digit form; a
58    /// rectangular grid uses the uppercase two-digit form.
59    static func encode(width: Int, height: Int, blocks: [Bool]) -> String? {
60        guard (minSide...maxSide).contains(width), (minSide...maxSide).contains(height),
61              blocks.count == width * height else {
62            return nil
63        }
64        let n = blocks.count
65        let symmetric = (0..<(n / 2)).allSatisfy { blocks[$0] == blocks[n - 1 - $0] }
66        let stored = symmetric ? Array(blocks.prefix((n + 1) / 2)) : blocks
67        let payload = Self.base64URLEncode(Self.packBits(stored))
68        if width == height {
69            let tag = symmetric ? "s" : "f"
70            return tag + String(width, radix: 36) + payload
71        }
72        let tag = symmetric ? "S" : "F"
73        return tag + String(width, radix: 36) + String(height, radix: 36) + payload
74    }
75
76    /// Reverses `encode`, or `nil` when the segment is malformed.
77    static func decode(_ segment: String) -> Grid? {
78        let chars = Array(segment)
79        guard let tag = chars.first else { return nil }
80
81        let width: Int
82        let height: Int
83        let payload: ArraySlice<Character>
84        switch tag {
85        case "s", "f":
86            guard chars.count >= 2,
87                  let side = Int(String(chars[1]), radix: 36),
88                  (minSide...maxSide).contains(side) else { return nil }
89            width = side
90            height = side
91            payload = chars[2...]
92        case "S", "F":
93            guard chars.count >= 3,
94                  let w = Int(String(chars[1]), radix: 36), (minSide...maxSide).contains(w),
95                  let h = Int(String(chars[2]), radix: 36), (minSide...maxSide).contains(h) else { return nil }
96            width = w
97            height = h
98            payload = chars[3...]
99        default:
100            return nil
101        }
102
103        let n = width * height
104        let symmetric = tag == "s" || tag == "S"
105        let storedCount = symmetric ? (n + 1) / 2 : n
106        guard let bytes = Self.base64URLDecode(String(payload)) else { return nil }
107        guard bytes.count == (storedCount + 7) / 8 else { return nil }
108        let bits = Self.unpackBits(bytes, count: storedCount)
109        guard bits.count == storedCount else { return nil }
110
111        var blocks = [Bool](repeating: false, count: n)
112        for k in 0..<n {
113            // The stored half holds cells 0..<⌈N/2⌉; every later cell mirrors
114            // its 180°-rotation partner, which lands inside the stored half.
115            blocks[k] = k < storedCount ? bits[k] : bits[n - 1 - k]
116        }
117        return Grid(width: width, height: height, blocks: blocks)
118    }
119
120    // MARK: - Bit packing
121
122    private static func packBits(_ bits: [Bool]) -> [UInt8] {
123        var bytes = [UInt8](repeating: 0, count: (bits.count + 7) / 8)
124        for (i, bit) in bits.enumerated() where bit {
125            bytes[i / 8] |= UInt8(0x80) >> (i % 8)
126        }
127        return bytes
128    }
129
130    private static func unpackBits(_ bytes: [UInt8], count: Int) -> [Bool] {
131        guard bytes.count * 8 >= count else { return [] }
132        return (0..<count).map { i in
133            bytes[i / 8] & (UInt8(0x80) >> (i % 8)) != 0
134        }
135    }
136
137    // MARK: - base64url
138
139    static func base64URLEncode(_ bytes: [UInt8]) -> String {
140        Data(bytes).base64EncodedString()
141            .replacingOccurrences(of: "+", with: "-")
142            .replacingOccurrences(of: "/", with: "_")
143            .replacingOccurrences(of: "=", with: "")
144    }
145
146    static func base64URLDecode(_ string: String) -> [UInt8]? {
147        var s = string
148            .replacingOccurrences(of: "-", with: "+")
149            .replacingOccurrences(of: "_", with: "/")
150        let remainder = s.count % 4
151        if remainder != 0 { s += String(repeating: "=", count: 4 - remainder) }
152        guard let data = Data(base64Encoded: s) else { return nil }
153        return [UInt8](data)
154    }
155}