nx_kp_break.nx source
↩ module page · 379 lines · 17384 B
1// nx_kp_break.nx -- KNUTH-PLASS OPTIMAL LINE BREAKING, integer-exact.
2//
3// WHY: every browser, and almost every renderer, breaks lines FIRST-FIT -- it fills the current line until the
4// next word does not fit, then breaks, and never reconsiders. That is a greedy choice made with no knowledge
5// of the rest of the paragraph, and it is why justified text on the web has rivers of white and books do not.
6// Knuth and Plass (1981, the TeX line breaker) instead model the paragraph as BOXES (words), GLUE (spaces that
7// can stretch and shrink) and PENALTIES (places a break is discouraged or encouraged), then choose the set of
8// breakpoints that minimises TOTAL badness over the WHOLE paragraph by dynamic programming. Accepting a
9// slightly worse line early to avoid a terrible line later is a trade a greedy algorithm cannot make.
10//
11// This is the piece CSS cannot reach. `hyphens:auto` and `text-align:justify` only make the browser's greedy
12// result less ugly; they do not change the algorithm. Owning the line breaker is what makes a Nishi reading
13// surface typographically book-grade rather than screen-grade.
14//
15// INTEGER-EXACT: badness is TeX's 100*r^3 evaluated in fixed point, so a paragraph lays out identically on
16// every host. Widths are in milli-units (one character = 1000) which keeps the arithmetic exact without float.
17//
18// nx_kp_break fit <cols> <text> -- optimal layout, one line per output line
19// nx_kp_break compare <cols> <text> -- Knuth-Plass vs greedy first-fit, with the measured difference
20// nx_kp_break selftest -- the gate
21// license_tier: ORIGINAL
22import "nx_gate_verdict.nx"
23import "nx_syscalls.nx"
24const KP_MAGIC_4000: i64 = 4000
25const KP_MAGIC_100000: i64 = 100000
26
27const KP_UNIT: i64 = 1000 // one character cell
28const KP_SP_NAT: i64 = 1000 // interword space: natural width
29const KP_SP_STRETCH: i64 = 500 // ... may stretch by half a space
30const KP_SP_SHRINK: i64 = 333 // ... may shrink by a third (TeX's plain.tex proportions)
31const KP_MAX_WORDS: i64 = 512
32const KP_INF: i64 = 1000000000 // "this line cannot be set" -- never a real cost
33const KP_BAD_CAP: i64 = 10000 // TeX treats anything past this as equally awful
34const KP_R_SCALE: i64 = 1000
35const KP_BAD_K: i64 = 100 // badness = 100 * r^3
36const KP_R_CUBE_DIV: i64 = 1000000000 // (r/1000)^3 == r^3 / 1e9
37const KP_LINE_PENALTY: i64 = 10 // a small per-line cost, so an equal-badness layout prefers fewer lines
38
39func kp_puts(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 }
40func kp_num(v: i64) -> i64 {
41 if v == 0 { sys_write(1, "0" as *u8, 1); return 0 }
42 var m: i64 = v
43 if m < 0 { sys_write(1, "-" as *u8, 1); m = 0 - m }
44 let t: *u8 = sys_mmap(32); var k: i64 = 0
45 while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 }
46 let o: *u8 = sys_mmap(32); var w: i64 = 0; var q: i64 = k - 1
47 while q >= 0 { o[w] = t[q]; w = w + 1; q = q - 1 }
48 sys_write(1, o, w); return 0
49}
50func kp_atoi(s: *u8) -> i64 {
51 var v: i64 = 0; var i: i64 = 0
52 while s[i] != (0 as u8) { let c: i64 = s[i] as i64; if c >= 48 { if c <= 57 { v = v*10 + (c-48) } } i = i + 1 }
53 return v
54}
55func kp_seq(a: *u8, b: *u8) -> i64 {
56 var i: i64 = 0
57 while 1 == 1 { if (a[i] as i64) != (b[i] as i64) { return 0 } if (a[i] as i64) == 0 { return 1 } i = i + 1 }
58 return 0
59}
60
61// split on spaces; wstart[]/wlen[] index into text, wid[] is the width in milli-units. returns word count.
62func kp_words(text: *u8, wstart: *i64, wlen: *i64, wid: *i64) -> i64 {
63 var n: i64 = 0
64 var i: i64 = 0
65 while text[i] != (0 as u8) {
66 if (text[i] as i64) != 32 {
67 let s: i64 = i
68 while text[i] != (0 as u8) { if (text[i] as i64) == 32 { break } i = i + 1 }
69 if n < KP_MAX_WORDS {
70 wstart[n] = s
71 wlen[n] = i - s
72 wid[n] = (i - s) * KP_UNIT
73 n = n + 1
74 }
75 }
76 if text[i] != (0 as u8) { if (text[i] as i64) == 32 { i = i + 1 } }
77 }
78 return n
79}
80
81// TeX badness for a line whose adjustment ratio is r (x1000).
82// r > 0 -> the line was stretched; r < 0 -> shrunk. r < -1000 means it needed more shrink than exists, which
83// is not a legal line at all, so it costs INF rather than merely a lot.
84func kp_badness(r: i64) -> i64 {
85 if r < 0 - KP_R_SCALE { return KP_INF }
86 var a: i64 = r
87 if a < 0 { a = 0 - a }
88 if a > KP_MAGIC_4000 { return KP_BAD_CAP }
89 let b: i64 = (KP_BAD_K * a * a * a) / KP_R_CUBE_DIV
90 if b > KP_BAD_CAP { return KP_BAD_CAP }
91 return b
92}
93
94// adjustment ratio (x1000) for setting words [i,j) on one line of `target` milli-units.
95// last=1 marks the final line, which is allowed to run short at no cost -- otherwise the optimiser would
96// pad the last line and every paragraph would end in a stretched, gappy line.
97func kp_ratio(wid: *i64, i: i64, j: i64, target: i64, last: i64) -> i64 {
98 var nat: i64 = 0
99 var k: i64 = i
100 while k < j { nat = nat + wid[k]; k = k + 1 }
101 let gaps: i64 = j - i - 1
102 if gaps < 0 { return 0 - KP_R_SCALE - 1 }
103 nat = nat + gaps * KP_SP_NAT
104 if nat == target { return 0 }
105 if nat < target {
106 if last == 1 { return 0 }
107 let st: i64 = gaps * KP_SP_STRETCH
108 if st <= 0 { return KP_R_SCALE * 4 }
109 return ((target - nat) * KP_R_SCALE) / st
110 }
111 let sh: i64 = gaps * KP_SP_SHRINK
112 if sh <= 0 { return 0 - KP_R_SCALE - 1 }
113 return 0 - (((nat - target) * KP_R_SCALE) / sh)
114}
115
116// THE OPTIMISER. best[j] = cheapest total cost to set words [0,j); prev[j] = the breakpoint that achieved it.
117// O(n^2) over breakpoints, which for a paragraph is nothing.
118func kp_optimal(wid: *i64, n: i64, target: i64, prev: *i64, best: *i64) -> i64 {
119 var j: i64 = 0
120 while j <= n { best[j] = KP_INF; prev[j] = 0 - 1; j = j + 1 }
121 best[0] = 0
122 j = 1
123 while j <= n {
124 var i: i64 = 0
125 while i < j {
126 if best[i] < KP_INF {
127 var last: i64 = 0
128 if j == n { last = 1 }
129 let r: i64 = kp_ratio(wid, i, j, target, last)
130 let b: i64 = kp_badness(r)
131 if b < KP_INF {
132 let cost: i64 = best[i] + b + KP_LINE_PENALTY
133 if cost < best[j] { best[j] = cost; prev[j] = i }
134 }
135 }
136 i = i + 1
137 }
138 j = j + 1
139 }
140 return best[n]
141}
142
143// greedy first-fit -- what a browser does. Fills until the next word does not fit, then breaks.
144// Returns total badness under the SAME cost function, so the two are comparable.
145func kp_greedy(wid: *i64, n: i64, target: i64, brk: *i64) -> i64 {
146 var total: i64 = 0
147 var nb: i64 = 0
148 var start: i64 = 0
149 var i: i64 = 0
150 var acc: i64 = 0
151 while i < n {
152 var add: i64 = wid[i]
153 if i > start { add = add + KP_SP_NAT }
154 if acc + add > target {
155 if i > start {
156 var last: i64 = 0
157 let r: i64 = kp_ratio(wid, start, i, target, last)
158 var b: i64 = kp_badness(r)
159 if b >= KP_INF { b = KP_BAD_CAP }
160 total = total + b + KP_LINE_PENALTY
161 brk[nb] = i; nb = nb + 1
162 start = i
163 acc = wid[i]
164 } else {
165 acc = acc + add
166 }
167 } else { acc = acc + add }
168 i = i + 1
169 }
170 if start < n {
171 let r: i64 = kp_ratio(wid, start, n, target, 1)
172 var b: i64 = kp_badness(r)
173 if b >= KP_INF { b = KP_BAD_CAP }
174 total = total + b + KP_LINE_PENALTY
175 brk[nb] = n; nb = nb + 1
176 }
177 return total
178}
179
180// walk prev[] back to a forward list of break positions. returns line count.
181func kp_backtrack(prev: *i64, n: i64, brk: *i64) -> i64 {
182 let tmp: *i64 = sys_mmap(8 * (KP_MAX_WORDS + 2)) as *i64
183 var c: i64 = 0
184 var j: i64 = n
185 while j > 0 {
186 if prev[j] < 0 { return 0 - 1 }
187 tmp[c] = j; c = c + 1
188 j = prev[j]
189 }
190 var k: i64 = 0
191 while k < c { brk[k] = tmp[c - 1 - k]; k = k + 1 }
192 return c
193}
194
195func kp_print_lines(text: *u8, wstart: *i64, wlen: *i64, brk: *i64, lines: i64) -> i64 {
196 var s: i64 = 0
197 var l: i64 = 0
198 while l < lines {
199 let e: i64 = brk[l]
200 kp_puts(" | " as *u8)
201 var w: i64 = s
202 while w < e {
203 sys_write(1, ((text as i64) + wstart[w]) as *u8, wlen[w])
204 if w < e - 1 { sys_write(1, " " as *u8, 1) }
205 w = w + 1
206 }
207 kp_puts("\n" as *u8)
208 s = e
209 l = l + 1
210 }
211 return 0
212}
213
214// worst single-line badness -- the metric a reader actually notices. A paragraph's total can look fine while
215// one line is a disaster, and it is the disaster line the eye lands on.
216func kp_worst(wid: *i64, n: i64, target: i64, brk: *i64, lines: i64) -> i64 {
217 var worst: i64 = 0
218 var s: i64 = 0
219 var l: i64 = 0
220 while l < lines {
221 let e: i64 = brk[l]
222 var last: i64 = 0
223 if l == lines - 1 { last = 1 }
224 let r: i64 = kp_ratio(wid, s, e, target, last)
225 var b: i64 = kp_badness(r)
226 if b >= KP_INF { b = KP_BAD_CAP }
227 if b > worst { worst = b }
228 s = e
229 l = l + 1
230 }
231 return worst
232}
233
234const KP_TEST_TEXT: *u8 = "In olden times when wishing still helped one there lived a king whose daughters were all beautiful but the youngest was so beautiful that the sun itself which has seen so much was astonished whenever it shone in her face"
235
236func kp_selftest() -> i64 {
237 gv_head("nx_kp_break -- does optimal line breaking actually beat what a browser does?" as *u8)
238 let ctr: *i64 = gv_ctr()
239 let wstart: *i64 = sys_mmap(8 * KP_MAX_WORDS) as *i64
240 let wlen: *i64 = sys_mmap(8 * KP_MAX_WORDS) as *i64
241 let wid: *i64 = sys_mmap(8 * KP_MAX_WORDS) as *i64
242 let prev: *i64 = sys_mmap(8 * (KP_MAX_WORDS + 2)) as *i64
243 let best: *i64 = sys_mmap(8 * (KP_MAX_WORDS + 2)) as *i64
244 let kbrk: *i64 = sys_mmap(8 * (KP_MAX_WORDS + 2)) as *i64
245 let gbrk: *i64 = sys_mmap(8 * (KP_MAX_WORDS + 2)) as *i64
246
247 let n: i64 = kp_words(KP_TEST_TEXT, wstart, wlen, wid)
248 let cols: i64 = 42
249 let target: i64 = cols * KP_UNIT
250
251 let ktot: i64 = kp_optimal(wid, n, target, prev, best)
252 let klines: i64 = kp_backtrack(prev, n, kbrk)
253 let gtot: i64 = kp_greedy(wid, n, target, gbrk)
254 var glines: i64 = 0
255 while glines < n { if gbrk[glines] == n { glines = glines + 1; break } glines = glines + 1 }
256 let kworst: i64 = kp_worst(wid, n, target, kbrk, klines)
257 let gworst: i64 = kp_worst(wid, n, target, gbrk, glines)
258
259 kp_puts(" paragraph: " as *u8); kp_num(n); kp_puts(" words at " as *u8); kp_num(cols); kp_puts(" columns\n" as *u8)
260 kp_puts(" knuth-plass total=" as *u8); kp_num(ktot); kp_puts(" worst_line=" as *u8); kp_num(kworst)
261 kp_puts(" lines=" as *u8); kp_num(klines); kp_puts("\n" as *u8)
262 kp_print_lines(KP_TEST_TEXT, wstart, wlen, kbrk, klines)
263 kp_puts(" greedy first-fit total=" as *u8); kp_num(gtot); kp_puts(" worst_line=" as *u8); kp_num(gworst)
264 kp_puts(" lines=" as *u8); kp_num(glines); kp_puts("\n" as *u8)
265 kp_print_lines(KP_TEST_TEXT, wstart, wlen, gbrk, glines)
266
267 // T1 CONTENT PRESERVATION, first: a beautiful layout that dropped a word is worthless. Breaks must be
268 // strictly increasing and must end exactly at n, which is what proves no word was lost or repeated.
269 var ordered: i64 = 1
270 var p: i64 = 0
271 var l: i64 = 0
272 while l < klines { if kbrk[l] <= p { ordered = 0 } p = kbrk[l]; l = l + 1 }
273 if p != n { ordered = 0 }
274 gv_check("every word appears exactly once, in order (breaks ascend and end at n)" as *u8, ordered, ctr)
275
276 // T2 LEGALITY: no line may need more shrink than its spaces have. An overfull line is a hard error in
277 // typesetting, not a matter of taste.
278 var legal: i64 = 1
279 var s2: i64 = 0
280 l = 0
281 while l < klines {
282 var last: i64 = 0
283 if l == klines - 1 { last = 1 }
284 let r: i64 = kp_ratio(wid, s2, kbrk[l], target, last)
285 if r < 0 - KP_R_SCALE { legal = 0 }
286 s2 = kbrk[l]
287 l = l + 1
288 }
289 gv_check("no line is overfull (every adjustment ratio is >= -1)" as *u8, legal, ctr)
290
291 // T3 THE SOTA CLAIM: optimal must never be WORSE than greedy under the same cost function. If it were,
292 // the dynamic program is wrong, because greedy's own solution is in the space it searches.
293 var notworse: i64 = 0
294 if ktot <= gtot { notworse = 1 }
295 gv_check("knuth-plass total cost is never worse than greedy first-fit" as *u8, notworse, ctr)
296
297 // T4 ANTI-VACUITY: "never worse" is satisfied by simply returning greedy's answer. This tooth demands a
298 // STRICT win on a real paragraph -- the trivial implementation that just copies greedy fails here.
299 var strictly: i64 = 0
300 if ktot < gtot { strictly = 1 }
301 gv_check("and on a real paragraph it is STRICTLY better (it is not just greedy in disguise)" as *u8, strictly, ctr)
302
303 // T5 WHAT THE READER SEES: the worst single line is what the eye catches. Optimal buys its total by
304 // refusing to leave one line badly stretched, so its worst line must not be worse than greedy's.
305 var worstok: i64 = 0
306 if kworst <= gworst { worstok = 1 }
307 gv_check("the WORST line is no worse than greedy's worst (rivers come from the worst line)" as *u8, worstok, ctr)
308
309 // T6 neg-control-degenerate-width: with a column wider than the whole paragraph, there is exactly one
310 // legal layout and BOTH algorithms must find it. If optimal still differed here, its advantage would be
311 // an artefact of the cost function rather than of the search.
312 let wide: i64 = KP_MAGIC_100000 * KP_UNIT
313 let k2: i64 = kp_optimal(wid, n, wide, prev, best)
314 let l2: i64 = kp_backtrack(prev, n, kbrk)
315 var degen: i64 = 0
316 if l2 == 1 { degen = 1 }
317 kp_puts(" neg-control at absurd width: optimal lines=" as *u8); kp_num(l2)
318 kp_puts(" cost=" as *u8); kp_num(k2); kp_puts("\n" as *u8)
319 gv_check("neg-control-degenerate-width: an absurdly wide column yields exactly one line" as *u8, degen, ctr)
320
321 return gv_verdict("KP-BREAK" as *u8, ctr, "optimal paragraph breaking measurably beats greedy first-fit on the same cost function" as *u8)
322}
323
324func main(argc: i64, argv: *i64) -> i64 {
325 if argc < 2 {
326 kp_puts("usage: nx_kp_break fit <cols> <text> | compare <cols> <text> | selftest\n" as *u8)
327 sys_exit(2); return 2
328 }
329 let verb: *u8 = argv[1] as *u8
330 if kp_seq(verb, "selftest" as *u8) == 1 { let rc: i64 = kp_selftest(); sys_exit(rc); return rc }
331 if argc < 4 {
332 kp_puts("usage: nx_kp_break fit <cols> <text> | compare <cols> <text> | selftest\n" as *u8)
333 sys_exit(2); return 2
334 }
335 let cols: i64 = kp_atoi(argv[2] as *u8)
336 if cols < 8 {
337 kp_puts("REFUSED: cols " as *u8); kp_num(cols); kp_puts(" is below 8 -- no legal layout exists for a column narrower than a word.\n" as *u8)
338 sys_exit(3); return 3
339 }
340 let text: *u8 = argv[3] as *u8
341 let target: i64 = cols * KP_UNIT
342 let wstart: *i64 = sys_mmap(8 * KP_MAX_WORDS) as *i64
343 let wlen: *i64 = sys_mmap(8 * KP_MAX_WORDS) as *i64
344 let wid: *i64 = sys_mmap(8 * KP_MAX_WORDS) as *i64
345 let prev: *i64 = sys_mmap(8 * (KP_MAX_WORDS + 2)) as *i64
346 let best: *i64 = sys_mmap(8 * (KP_MAX_WORDS + 2)) as *i64
347 let kbrk: *i64 = sys_mmap(8 * (KP_MAX_WORDS + 2)) as *i64
348 let n: i64 = kp_words(text, wstart, wlen, wid)
349 if n <= 0 { kp_puts("REFUSED: no words in input\n" as *u8); sys_exit(3); return 3 }
350 let ktot: i64 = kp_optimal(wid, n, target, prev, best)
351 let klines: i64 = kp_backtrack(prev, n, kbrk)
352 if klines < 0 {
353 kp_puts("REFUSED: no legal layout at " as *u8); kp_num(cols)
354 kp_puts(" columns -- some word is wider than the column.\n" as *u8)
355 sys_exit(3); return 3
356 }
357 if kp_seq(verb, "fit" as *u8) == 1 {
358 kp_puts("KP-FIT cols=" as *u8); kp_num(cols); kp_puts(" words=" as *u8); kp_num(n)
359 kp_puts(" lines=" as *u8); kp_num(klines); kp_puts(" total_badness=" as *u8); kp_num(ktot); kp_puts("\n" as *u8)
360 kp_print_lines(text, wstart, wlen, kbrk, klines)
361 sys_exit(0); return 0
362 }
363 if kp_seq(verb, "compare" as *u8) == 1 {
364 let gbrk: *i64 = sys_mmap(8 * (KP_MAX_WORDS + 2)) as *i64
365 let gtot: i64 = kp_greedy(wid, n, target, gbrk)
366 var glines: i64 = 0
367 while glines < n { if gbrk[glines] == n { glines = glines + 1; break } glines = glines + 1 }
368 kp_puts("KP-COMPARE cols=" as *u8); kp_num(cols); kp_puts(" words=" as *u8); kp_num(n); kp_puts("\n" as *u8)
369 kp_puts(" knuth-plass total=" as *u8); kp_num(ktot); kp_puts(" worst=" as *u8); kp_num(kp_worst(wid,n,target,kbrk,klines))
370 kp_puts(" lines=" as *u8); kp_num(klines); kp_puts("\n" as *u8)
371 kp_print_lines(text, wstart, wlen, kbrk, klines)
372 kp_puts(" greedy total=" as *u8); kp_num(gtot); kp_puts(" worst=" as *u8); kp_num(kp_worst(wid,n,target,gbrk,glines))
373 kp_puts(" lines=" as *u8); kp_num(glines); kp_puts("\n" as *u8)
374 kp_print_lines(text, wstart, wlen, gbrk, glines)
375 sys_exit(0); return 0
376 }
377 kp_puts("usage: nx_kp_break fit <cols> <text> | compare <cols> <text> | selftest\n" as *u8)
378 sys_exit(2); return 2
379}