750 lines
53 KiB
Python
750 lines
53 KiB
Python
"""Chinese Manim film; all timings shown come from data/benchmarks.json."""
|
||
from pathlib import Path
|
||
import json
|
||
import os
|
||
import re
|
||
|
||
import manimpango
|
||
import numpy as np
|
||
from manim import *
|
||
|
||
HERE = Path(__file__).resolve().parent
|
||
DATA = json.loads((HERE / 'data/benchmarks.json').read_text())
|
||
BG, INK, MUTED = '#0B1220', '#E8EEF7', '#94A3B8'
|
||
CYAN, MINT, AMBER, PANEL = '#38BDF8', '#34D399', '#FBBF24', '#172235'
|
||
|
||
# WSL may use an installed Windows font without copying/distributing it.
|
||
font_path = os.environ.get('SLIME_FONT_PATH', '/mnt/c/Windows/Fonts/msyh.ttc')
|
||
if Path(font_path).is_file():
|
||
manimpango.register_font(font_path)
|
||
fonts = manimpango.list_fonts()
|
||
FONT = next((f for f in ('Microsoft YaHei', 'Noto Sans CJK SC', 'WenQuanYi Zen Hei') if f in fonts), None)
|
||
if FONT is None:
|
||
raise RuntimeError('需要中文字体：安装 Noto Sans CJK，或设置 SLIME_FONT_PATH 指向中文字体。')
|
||
|
||
|
||
def text(value, size=28, color=INK, max_width=12):
|
||
obj = Text(str(value), font=FONT, font_size=size, color=color)
|
||
if obj.width > max_width:
|
||
obj.scale_to_fit_width(max_width)
|
||
return obj
|
||
|
||
|
||
MATH_TEMPLATE = TexTemplate(
|
||
documentclass=r"\documentclass[preview]{standalone}",
|
||
preamble=r"\usepackage{amsmath}\usepackage{amssymb}",
|
||
)
|
||
|
||
|
||
def formula_tex(value, size=32, color=INK, max_width=12):
|
||
obj = MathTex(value, tex_template=MATH_TEMPLATE, font_size=size, color=color)
|
||
if obj.width > max_width:
|
||
obj.scale_to_fit_width(max_width)
|
||
return obj
|
||
|
||
|
||
def subtitle_text(value, max_width=12.4):
|
||
"""Mix Pango Chinese prose and actual MathTex for $...$ inline formulas."""
|
||
if value.count('$') % 2:
|
||
raise ValueError(f'Unbalanced inline math: {value}')
|
||
parts = VGroup()
|
||
for segment in re.split(r'(\$[^$]+\$)', value):
|
||
if not segment.strip():
|
||
continue
|
||
if segment.startswith('$') and segment.endswith('$'):
|
||
parts.add(formula_tex(segment[1:-1], 30))
|
||
else:
|
||
parts.add(text(segment.strip(), 24))
|
||
parts.arrange(RIGHT, buff=.055, aligned_edge=DOWN)
|
||
if parts.width > max_width:
|
||
parts.scale_to_fit_width(max_width)
|
||
return parts
|
||
|
||
|
||
def grid(n=5, side=.48, color=CYAN):
|
||
return VGroup(*[
|
||
Square(side_length=side, stroke_color=color, stroke_width=1.3,
|
||
fill_color=PANEL, fill_opacity=1).move_to(
|
||
[(j-(n-1)/2)*side, ((n-1)/2-i)*side, 0])
|
||
for i in range(n) for j in range(n)
|
||
])
|
||
|
||
|
||
def box(label, width=2.5, height=.65, color=CYAN):
|
||
frame = RoundedRectangle(width=width, height=height, corner_radius=.10,
|
||
stroke_color=color, fill_color=PANEL, fill_opacity=1)
|
||
return VGroup(frame, text(label, 22, color, width-.2))
|
||
|
||
|
||
class FilmBase(Scene):
|
||
def setup(self):
|
||
self.camera.background_color = BG
|
||
self.cues = []
|
||
self.chapters = []
|
||
self.subtitle = None
|
||
self.timeline_frames = 0
|
||
|
||
def play(self, *args, **kwargs):
|
||
super().play(*args, **kwargs)
|
||
# Cached Cairo segments advance by requested seconds, while fresh
|
||
# segments advance by encoded frames. Keep exports on the frame clock
|
||
# in both cases, including a timeline-only replay of the same scene.
|
||
dt = 1 / self.camera.frame_rate
|
||
if self.is_current_animation_frozen_frame():
|
||
frames = int(self.duration / dt)
|
||
else:
|
||
frames = len(np.arange(0, self.duration, dt))
|
||
self.timeline_frames += frames
|
||
self.renderer.time = self.timeline_frames * dt
|
||
|
||
def chapter(self, number, title, tag):
|
||
if self.mobjects:
|
||
self.play(*[FadeOut(m) for m in list(self.mobjects)], run_time=.45)
|
||
self.subtitle = None
|
||
self.chapters.append({'title': title, 'start': float(self.time)})
|
||
heading = text(title, 34).to_edge(UP, buff=.35).align_to(LEFT*6.5, LEFT)
|
||
badge = text(number, 20, MINT).to_corner(UR, buff=.4)
|
||
footer = text(tag, 17, MUTED).move_to([0, -2.93, 0])
|
||
line = Line([-6.5, -3.16, 0], [6.5, -3.16, 0], color=PANEL)
|
||
self.chrome = (heading, badge, footer, line)
|
||
self.play(FadeIn(heading), FadeIn(badge), FadeIn(footer), Create(line), run_time=.6)
|
||
|
||
def say(self, caption, seconds=5, *, display=None):
|
||
if self.subtitle is not None:
|
||
self.remove(self.subtitle)
|
||
self.subtitle = subtitle_text(display if display is not None else caption).move_to([0, -3.58, 0])
|
||
self.add(self.subtitle)
|
||
self.cues.append({'start': float(self.time), 'end': float(self.time + seconds), 'text': caption, 'display': display if display is not None else caption})
|
||
self.wait(seconds)
|
||
|
||
|
||
def page(self, title, equations=(), notes=(), *, kind='general'):
|
||
heading = text(title, 28, CYAN).move_to([0, 2.05, 0])
|
||
rows = VGroup(*[formula_tex(eq, 32, color, 11.8) for eq, color in equations],
|
||
*[text(note, 26, color, 11.8) for note, color in notes])
|
||
rows.arrange(DOWN, buff=.38).move_to([0, .05, 0])
|
||
if rows.height > 3.5:
|
||
rows.scale_to_fit_height(3.5)
|
||
objects = VGroup(heading, rows)
|
||
if kind != 'general':
|
||
label = {'example': '贯穿案例 · 同一个 5×5 窗口',
|
||
'measurement': '实测案例 · 仅对应指定输入'}[kind]
|
||
marker = text(label, 18, AMBER).move_to([0, 2.65, 0])
|
||
quote_line = Line([-6.3, 1.65, 0], [-6.3, -2.05, 0], color=AMBER, stroke_width=4)
|
||
objects.add(marker, quote_line)
|
||
self.play(FadeIn(objects), run_time=.6)
|
||
return objects
|
||
|
||
def code_page(self, title, source, notes=()):
|
||
heading = text(title, 28, CYAN).move_to([0, 2.25, 0])
|
||
source_lines = source.splitlines()
|
||
lines = VGroup(*[Text(line.lstrip() or ' ', font='DejaVu Sans Mono', font_size=21, color=INK)
|
||
for line in source_lines])
|
||
lines.arrange(DOWN, aligned_edge=LEFT, buff=.10)
|
||
for row, line in zip(lines, source_lines):
|
||
row.shift(RIGHT * .13 * (len(line) - len(line.lstrip())))
|
||
if lines.width > 11.5:
|
||
lines.scale_to_fit_width(11.5)
|
||
if lines.height > 3.65:
|
||
lines.scale_to_fit_height(3.65)
|
||
lines.move_to([0, .10, 0])
|
||
footer = text(' · '.join(notes), 20, MUTED).move_to([0, -2.25, 0])
|
||
self.play(FadeIn(VGroup(heading, lines, footer)), run_time=.6)
|
||
|
||
def chart(self, key, labels):
|
||
d = DATA[key]
|
||
before, after = d['before_ms'], d['after_ms']
|
||
max_width = 6.4
|
||
# Exact linear scale, including very small optimized bars.
|
||
baseline = -3.4
|
||
items = VGroup()
|
||
for i, (label, value, color) in enumerate(zip(labels, (before, after), (AMBER, MINT))):
|
||
y = .5-i*1.0
|
||
name = text(label, 24, max_width=2.5).move_to([-5, y, 0])
|
||
bar = Rectangle(width=max_width*value/before, height=.4,
|
||
stroke_width=0, fill_color=color, fill_opacity=1)
|
||
bar.move_to([baseline+bar.width/2, y, 0])
|
||
value_text = text(f'{value:.3f} ms', 23, color).next_to(bar, RIGHT, buff=.18)
|
||
items.add(name, bar, value_text)
|
||
ratio = formula_tex(rf'{before/after:.2f}\times', 46, MINT).move_to([0, -1.45, 0])
|
||
condition = text(d['workload'], 25, CYAN).move_to([0, 1.55, 0])
|
||
metric_label = {
|
||
'A': 'CPU 搜索 / GPU scan · 中位数 / 5 轮 · CPU 16 逻辑线程',
|
||
'B': 'GPU kernel · 中位数 / 5 轮 · 同组完整命中列表一致',
|
||
'C': 'GPU kernel · 中位数 / 100 轮 · 同组完整命中列表一致',
|
||
}[key]
|
||
metric = text(metric_label, 19, MUTED).move_to([0, -2.2, 0])
|
||
self.play(FadeIn(condition), LaggedStart(*[FadeIn(m) for m in items], lag_ratio=.08),
|
||
FadeIn(ratio), FadeIn(metric), run_time=1.8)
|
||
return VGroup(condition, items, ratio, metric)
|
||
|
||
|
||
def problem(self):
|
||
self.chapter('02', 'CPU：先把正确答案算出来', '源码：01_cpu.cpp · 原始 Java Random 语义 · 不通过便立即退出')
|
||
g = grid(5, .48).move_to([-4.7, .15, 0])
|
||
source = '''for worldSeed in seeds:
|
||
for (x, z) in positions:
|
||
allSlime = true
|
||
for (dx, dz) in requiredOffsets:
|
||
if not isSlimeChunk(worldSeed, x + dx, z + dz):
|
||
allSlime = false
|
||
break
|
||
if allSlime:
|
||
record(worldSeed, x, z)'''
|
||
code = VGroup(*[Text(line.lstrip(), font='DejaVu Sans Mono', font_size=17,
|
||
color=AMBER if 'break' in line else INK)
|
||
for line in source.splitlines()])
|
||
code.arrange(DOWN, aligned_edge=LEFT, buff=.15)
|
||
for row, line in zip(code, source.splitlines()):
|
||
row.shift(RIGHT * .105 * (len(line) - len(line.lstrip())))
|
||
code.scale_to_fit_width(8.6).move_to([2.15, .25, 0])
|
||
self.play(FadeIn(g), FadeIn(code), run_time=1)
|
||
self.play(g[0].animate.set_fill(MINT, opacity=.6), g[1].animate.set_fill(AMBER, opacity=.8), run_time=.8)
|
||
self.say('对每个 seed，遍历锚点，再判断锚点周围的 25 格。', 6)
|
||
self.say('一格不满足就停止，只有全部通过才记录结果。', 6)
|
||
note = text('CPU 基线也使用多线程：实测为 16 个逻辑线程', 23, MUTED).move_to([0, -2.1, 0])
|
||
self.play(FadeIn(note))
|
||
self.say('保留 CPU 实现，后面的优化都要核对相同搜索结果。', 6)
|
||
|
||
|
||
def cuda(self):
|
||
self.chapter('03', 'CUDA：每个 thread 负责一个 seed', '源码：02_cuda_seed.cuh · 图中只展示少量线程，实际启动更多线程')
|
||
workers = VGroup(*[box(f'thread {i}', 1.45, .65) for i in range(6)]).arrange(RIGHT, buff=.3).move_to([0, 1.3, 0])
|
||
seeds = VGroup(*[text(f'seed {i}', 23, MINT) for i in range(6)]).arrange(RIGHT, buff=.75).move_to([0, .2, 0])
|
||
maps = VGroup(*[grid(3, .24) for _ in range(6)]).arrange(RIGHT, buff=1.0).move_to([0, -1.1, 0])
|
||
arrows = VGroup(*[Arrow(w.get_bottom(), s.get_top(), buff=.1, color=MUTED) for w,s in zip(workers,seeds)])
|
||
self.play(FadeIn(workers), FadeIn(seeds), FadeIn(maps), Create(arrows), run_time=1.5)
|
||
for cell in range(3):
|
||
self.play(*[g[cell].animate.set_fill(MINT, opacity=.65) for g in maps], run_time=.35)
|
||
self.say('把 seed 分给 GPU 线程；每个线程仍然遍历整个坐标窗口。', 7)
|
||
self.say('相同的检查逻辑，被更多线程同时执行。', 5)
|
||
self.play(FadeOut(VGroup(workers, seeds, maps, arrows)), run_time=.6)
|
||
self.chart('A', ('CPU', 'CUDA / seed'))
|
||
self.say('A 组：CPU 搜索 3550 毫秒，GPU scan 111 毫秒，约快 32 倍。', 8)
|
||
self.say('这里比较的是搜索时间和 GPU scan，不能改拿 kernel 时间计算这个倍数。', 7)
|
||
|
||
|
||
def mapping(self):
|
||
self.chapter('04', '改变分工：固定坐标，遍历 seed', '源码：03_cuda_position.cuh · 坐标项存在线程私有数组中 · 不引入全局坐标表')
|
||
self.coordinate_identity()
|
||
left = VGroup(box('thread → seed', 3.2, color=AMBER),
|
||
text('for each (x, z)', 25), text('compute F(x+dx), G(z+dz)', 22, AMBER)).arrange(DOWN, buff=.35).move_to([-3.4, .6, 0])
|
||
right = VGroup(box('thread → (x, z)', 3.2, color=MINT),
|
||
text('precompute 5 X + 5 Z terms', 22, MINT),
|
||
text('for each seed: reuse terms', 23)).arrange(DOWN, buff=.35).move_to([3.1, .6, 0])
|
||
arrow = Arrow([-1.2, .5, 0], [1.0, .5, 0], color=CYAN)
|
||
self.play(FadeIn(left), FadeIn(right), GrowArrow(arrow), run_time=1.2)
|
||
formula = formula_tex(r'T(x+\Delta x,z+\Delta z)=F(x+\Delta x)+G(z+\Delta z)', 34, CYAN).move_to([0, -1.7, 0])
|
||
self.play(FadeIn(formula))
|
||
self.say('坐标固定之后，X 和 Z 的多项式在 seed 循环外计算。', 7, display='坐标固定之后，$X$ 和 $Z$ 的多项式在 seed 循环外计算。')
|
||
self.say('同一份坐标项，可以在许多 seed 上重复使用。', 6)
|
||
self.play(FadeOut(VGroup(left, right, arrow, formula)))
|
||
self.chart('B', ('CUDA / seed', 'CUDA / coordinate'))
|
||
self.say('B 组扩大到 4097×4097；相同任务下，从 31.599 秒降到 17.600 秒。', 8, display='B 组扩大到 $4097\\times4097$；相同任务下，从 31.599 秒降到 17.600 秒。')
|
||
self.say('这一组重新测量两个版本，只在组内比较：约快 1.80 倍。', 7)
|
||
|
||
|
||
def outer(self):
|
||
self.chapter('05', 'Outer sum：邻居也可以共享坐标项', '源码：04_cuda_outer_sum.cuh · 实际 block 为 16×16 · 示意图简化为 5×5')
|
||
self.outer_identity()
|
||
g = grid(5, .54).move_to([0, .1, 0])
|
||
xs = VGroup(*[formula_tex(rf'F(x+{i})', 28, CYAN).move_to([g[i*5].get_x()-.75, g[i*5].get_y(), 0]) for i in range(5)])
|
||
zs = VGroup(*[formula_tex(rf'G(z+{i})', 28, MINT).move_to([g[i].get_x(), g[i].get_y()+.65, 0]) for i in range(5)])
|
||
self.play(FadeIn(g), FadeIn(xs), FadeIn(zs), run_time=1)
|
||
self.play(*[g[2*5+j].animate.set_fill(CYAN, opacity=.4) for j in range(5)], run_time=.7)
|
||
self.say('固定 X 的坐标项沿一整行复用；固定 Z 的项沿一整列复用。', 7, display='固定 $X$ 的坐标项沿一整行复用；固定 $Z$ 的项沿一整列复用。')
|
||
self.play(*[g[i*5+3].animate.set_fill(MINT, opacity=.4) for i in range(5)], run_time=.7)
|
||
formula = formula_tex(r'T(x,z)=F(x)+G(z)', 36, MINT, 4.5).move_to([3.9, -.1, 0])
|
||
self.play(FadeIn(formula))
|
||
self.say('把两条轴放进 shared memory，再用 outer sum 组合每格的输入。', 7)
|
||
self.play(FadeOut(VGroup(g, xs, zs, formula)))
|
||
note = text('16×16 锚点 + 5×5 图案 → 每条轴需要 20 项（包含 halo）', 22, MUTED).move_to([0, 2.1, 0])
|
||
self.add(note)
|
||
self.chart('C', ('fixed coordinate', 'tiled outer sum'))
|
||
self.say('C 组固定一个 seed；kernel 从 2.715 毫秒降到 1.598 毫秒。', 8)
|
||
self.say('重新测量 03 再比较 04，约快 1.70 倍；不同负载的倍数不能连乘。', 7)
|
||
self.say('这段共享轴项属于前四版的演进。当前最终搜索入口逐格计算坐标项，后面只使用坐标可分离的数学关系。', 12)
|
||
|
||
|
||
def coordinate_identity(self):
|
||
intro = text('回到坐标项：按 X、Z 分组', 25, MUTED).move_to([0,2.05,0])
|
||
original = formula_tex(
|
||
r'T(x,z)=\operatorname{J}_{32}(4987142x^2)+\operatorname{J}_{32}(5947611x)'
|
||
r'+4392871\operatorname{J}_{32}(z^2)+\operatorname{J}_{32}(389711z)',
|
||
34).move_to([0,1.25,0])
|
||
wrap = VGroup(
|
||
formula_tex(r'\operatorname{J}_{32}(\xi)=((\xi+2^{31})\bmod 2^{32})-2^{31}', 30, MUTED),
|
||
text('32 位回绕 → 有符号解释 → 提升到 64 位', 21, MUTED),
|
||
).arrange(DOWN, buff=.15).move_to([0,-1.9,0])
|
||
self.play(FadeIn(intro), FadeIn(original), FadeIn(wrap), run_time=1.1)
|
||
self.say('把原始坐标公式写完整，并保留 Java 的 32 位回绕位置。', 7)
|
||
x_part = formula_tex(
|
||
r'F(x)=\operatorname{J}_{32}(4987142x^2)+\operatorname{J}_{32}(5947611x)',
|
||
36, CYAN).move_to([0,.35,0])
|
||
z_part = formula_tex(
|
||
r'G(z)=4392871\operatorname{J}_{32}(z^2)+\operatorname{J}_{32}(389711z)',
|
||
36, MINT).move_to([0,-.55,0])
|
||
self.play(FadeIn(x_part), FadeIn(z_part), run_time=1)
|
||
self.say('前两项只依赖 X，后两项只依赖 Z，把它们分别命名为 F 和 G。', 8, display='前两项只依赖 $X$，后两项只依赖 $Z$，把它们分别命名为 $F$ 和 $G$。')
|
||
separated = formula_tex(r'T(x,z)=F(x)+G(z)', 44, AMBER).move_to(original)
|
||
self.play(Transform(original, separated), run_time=1)
|
||
self.say('没有 X 与 Z 相乘的混合项，所以坐标输入能精确拆成两条独立的轴。', 8, display='没有 $X$ 与 $Z$ 相乘的混合项，所以坐标输入能精确拆成两条独立的轴。')
|
||
self.say('这只是按变量重新分组，不是近似；每一项的整数回绕规则都保持原样。', 7)
|
||
self.play(FadeOut(VGroup(intro,original,x_part,z_part,wrap)), run_time=.6)
|
||
|
||
|
||
def outer_identity(self):
|
||
self.page('两条轴的交点就是两项之和', [
|
||
(r'T(x,z)=F(x)+G(z)', CYAN),
|
||
(r'\begin{array}{c|ccc}&G(z)&G(z+1)&G(z+2)\\\hline F(x)&F(x)+G(z)&F(x)+G(z+1)&F(x)+G(z+2)\\ F(x+1)&F(x+1)+G(z)&F(x+1)+G(z+1)&F(x+1)+G(z+2)\end{array}', INK),
|
||
], [('先准备两条轴，再按需要组合；随机数判断仍逐格执行', MINT)])
|
||
self.say('横轴和纵轴各算一次。表中每个交点都是对应两项之和，相邻线程不必重新计算相同的坐标多项式。', 12)
|
||
self.clear_body()
|
||
|
||
def clear_body(self):
|
||
body = [m for m in self.mobjects if m not in self.chrome and m is not self.subtitle]
|
||
if body:
|
||
self.play(*[FadeOut(m) for m in body], run_time=.4)
|
||
|
||
def measured_effect(self, key, title, notes=()):
|
||
self.clear_body()
|
||
d = DATA[key]
|
||
return self.page(title, [
|
||
(rf'{d["before_ms"]:.3f}\,\mathrm{{ms}}\ \longrightarrow\ {d["after_ms"]:.3f}\,\mathrm{{ms}}', MINT),
|
||
(rf'{d["before_ms"]/d["after_ms"]:.2f}\times', AMBER),
|
||
], [(d['workload'], INK), (d['metric'], MUTED), *notes], kind='measurement')
|
||
|
||
def opening(self):
|
||
self.chapter('01', '史莱姆区块：先看单个区块如何判定', 'DOCUMENT.md 第 0 节 · 坐标单位为区块，每块水平覆盖 16×16 方块')
|
||
self.code_page('直接使用 Java Random', '''boolean isSlimeChunk(long worldSeed, int x, int z) {
|
||
long coordinateTerm = (long) (x * x * 4987142)
|
||
+ (long) (x * 5947611)
|
||
+ (long) (z * z) * 4392871L
|
||
+ (long) (z * 389711);
|
||
long randomSeed = (worldSeed + coordinateTerm) ^ 987234911L;
|
||
return new Random(randomSeed).nextInt(10) == 0;
|
||
}''', ['世界种子 + 区块坐标 → 返回 0 才是史莱姆区块'])
|
||
self.say('先看一个区块。坐标项与世界种子相加，异或后初始化 Random，再调用 nextInt 十。返回零就是史莱姆区块。', 13)
|
||
self.say('同一个世界种子、同一个坐标，总得到相同结果。我们先加快这种检查，再研究如何反向搜索种子。', 11)
|
||
self.clear_body()
|
||
self.code_page('展开 Random：先初始化 48 位状态', '''final long A = 0x5DEECE66DL;
|
||
final long mask48 = (1L << 48) - 1;
|
||
long randomSeed = (worldSeed + coordinateTerm) ^ 987234911L;
|
||
long u = (randomSeed ^ A) & mask48;
|
||
// C = 987234911L ^ A：两次 XOR 合并后的常量''', ['A：固定乘数；u：初始状态；& mask48：只留低 48 位'])
|
||
self.say('Random 初始化还会再异或一次固定常量 A，并保留低四十八位，得到初始状态 u。两次异或合并后的常量记为 C。', 13,
|
||
display=r'初始化得到 $u$；两次 XOR 合并为 $C=987234911\mathbin{\mathrm{xor}}A$。')
|
||
self.clear_body()
|
||
self.code_page('展开 Random：更新、取数、必要时重抽', '''while (true) {
|
||
long v = (A * u + 11) & mask48;
|
||
int q = (int) (v >>> 17);
|
||
int value = q % 10;
|
||
if ((long) q - value + 9 <= 0x7FFFFFFFL) {
|
||
return value == 0;
|
||
}
|
||
u = v; // 本次输出被拒绝，从当前状态继续取数
|
||
}''', ['v：更新后的状态；q：高 31 位原始输出'])
|
||
self.say('状态乘 A 加十一，截成四十八位，再取高三十一位。通常取除以十的余数；极少数过大的输出会被拒绝，再更新一次。', 14)
|
||
self.clear_body()
|
||
self.page('坐标项的完整公式与整数回绕', [
|
||
(r'J_{32}(\xi)=((\xi+2^{31})\bmod2^{32})-2^{31}', MUTED),
|
||
(r'T(x,z)=J_{32}(4987142x^2)+J_{32}(5947611x)', CYAN),
|
||
(r'\qquad+4392871J_{32}(z^2)+J_{32}(389711z)', CYAN),
|
||
], [('J₃₂：保留低 32 位，再按有符号整数解释', INK),
|
||
('X 的平方乘系数后转 long；Z 的平方先转 long 再乘系数', AMBER)])
|
||
self.say('坐标项的数学公式放在这里。J 三十二保留 Java 的整数回绕；X 和 Z 转成长整数的位置不同，必须保留。', 13)
|
||
|
||
def random_bridge(self):
|
||
self.chapter('06', 'Random：状态更新与 48 位等价关系', 'DOCUMENT.md 第 5 节 · 从加快枚举转向减少候选')
|
||
self.page('先把单个区块的随机数过程写成公式', [
|
||
(r'A=\mathtt{0x5DEECE66D},\quad C=A\mathbin{\mathrm{xor}}987234911', MUTED),
|
||
(r'u=((w+T(x,z))\mathbin{\mathrm{xor}}C)\bmod2^{48}', CYAN),
|
||
(r'v=(Au+11)\bmod2^{48},\qquad q=v\gg17', MINT),
|
||
], [('w：世界种子的低 48 位；u、v：更新前后的状态', INK),
|
||
('q：首次 31 位输出；普通候选要求 q 能被 10 整除', AMBER)])
|
||
self.say('坐标公式已经解释过。现在只看 Random：先初始化 u，乘 A 加十一得到 v，再取高三十一位 q。', 11)
|
||
self.say('前面四个版本仍检查同一批候选。后面利用这些确定的运算，排除不可能的种子，并直接求出部分未知位。', 12)
|
||
self.clear_body()
|
||
self.page('史莱姆判断只看世界种子的低 48 位', [
|
||
(r'w\in[0,2^{48}),\qquad 2^{48}=281474976710656', CYAN),
|
||
(r'\mathrm{worldSeed}\mapsto\mathrm{worldSeed}+k2^{48}', INK),
|
||
], [('初始化只保留低 48 位，因此同一坐标上的完整随机序列相同', MINT),
|
||
('这是史莱姆判定等价，不表示整个 Minecraft 世界相同', MUTED)])
|
||
self.say('初始化只保留四十八位。因此世界种子相差二的四十八次方的整数倍，在同一坐标上得到相同随机序列。', 12)
|
||
self.say('这只是史莱姆判断等价。候选生成暂按首次输出分析，完整 Java 验证和覆盖边界在最后交代。', 11)
|
||
|
||
def normalize(self):
|
||
self.chapter('07', '有效种子：先反推关系，再引入窗口', 'DOCUMENT.md 第 6 节 · 此处开始统一的 5×5 贯穿案例')
|
||
self.page('先看一个固定区块：求 s，再恢复 w', [
|
||
(r's=(w+T(x,z))\bmod2^{48}', CYAN),
|
||
(r'u=(s\mathbin{\mathrm{xor}}C)\bmod2^{48}', INK),
|
||
(r'w=(s-T(x,z))\bmod2^{48}', MINT),
|
||
], [('坐标固定后，T(x,z) 已知；先搜索有效种子 s', INK),
|
||
('可逆换元，不删除候选', AMBER)])
|
||
self.say('先只看一个固定区块。把世界种子加坐标项记成有效种子 s。求到 s 后，再减去已知坐标项就能反推 w。', 13)
|
||
self.clear_body()
|
||
self.page('现在扩展到同一个实心 5×5 窗口', [
|
||
(r'51069\le x\le51073,\qquad419124\le z\le419128', CYAN),
|
||
(r'\begin{array}{c|rrrrr}z\backslash x&51069&51070&51071&51072&51073\\\hline419124&0&1&2&3&4\\419125&5&6&7&8&9\\419126&10&11&12&13&14\\419127&15&16&17&18&19\\419128&20&21&22&23&24\end{array}', INK),
|
||
], [('0 号格是最小 X、最小 Z 的锚点；要求全部 25 格通过', MINT)], kind='example')
|
||
self.say('反推关系建立后，再引入窗口。锚点是五万一千零六十九、四十一万九千一百二十四，沿 X 优先编号零到二十四。', 13)
|
||
self.say('后面每个数值例子都使用这一个窗口。只展示部分格子时，仍然来自这张表。', 10)
|
||
self.clear_body()
|
||
self.page('其他格子只需补上相对坐标项', [
|
||
(r'd_i=(T_i-T_0)\bmod2^{48},\qquad d_0=0', MINT),
|
||
(r's=(w+T_0)\bmod2^{48}', CYAN),
|
||
(r'w+T_i\equiv s+d_i\pmod{2^{48}}', INK),
|
||
(r'u_i=((s+d_i)\mathbin{\mathrm{xor}}C)\bmod2^{48}', INK),
|
||
], [('dᵢ：该格坐标项与锚点的差；Tᵢ：第 i 格的坐标项', MUTED)])
|
||
self.say('窗口各格共享同一个世界种子。有效种子已经吸收锚点项，其他格只需补上坐标项的差，记作 d 下标 i。', 13)
|
||
self.say('把各格坐标项简记为 T 下标 i，锚点项为 T 零。以后统一从 s 加 d 计算，求到 s 后减回 T 零。', 12)
|
||
self.clear_body()
|
||
self.page('贯穿案例：计算坐标项，再求相对项', [
|
||
(r'J_{32}(4987142\cdot51069^2)=-1799531722', MUTED),
|
||
(r'T_0=-1883366190470623,\quad T_1=-1883363608967202', CYAN),
|
||
(r'd_1=T_1-T_0=2581503421', MINT),
|
||
(r's=(w-1883366190470623)\bmod2^{48}', INK),
|
||
], [('现在 s、w 尚未知；接下来先找 s 的低 18 位', AMBER)], kind='example')
|
||
self.say('前两格坐标项按 Java 回绕算出，相减得到右邻格的相对项二十五亿八千一百五十万三千四百二十一。', 12)
|
||
self.say('现在仍不知道 s 和 w。下一步先筛出可能的低十八位，逐步求回完整有效种子。', 10)
|
||
|
||
def low_roots(self):
|
||
self.chapter('08', '第一次筛选：只枚举有效种子的低 18 位', '本章输出：低位根 p；代码中称为 root')
|
||
self.page('偶数条件只依赖状态的第 17 位', [
|
||
(r's=p+2^{18}m+2^{35}h', CYAN),
|
||
(r'q_i=v_i\gg17', INK),
|
||
(r'\operatorname{bit}_0(q_i)=\operatorname{bit}_{17}(v_i)', MINT),
|
||
], [('p：低 18 位；m：中间 17 位；h：高 13 位', CYAN),
|
||
('能被 10 整除，首先必须是偶数', AMBER)])
|
||
self.say('把有效种子拆成低十八位 p、中间十七位 m 和高十三位 h。', 8,
|
||
display=r'有效种子拆成低 18 位 $p$、中间 17 位 $m$、高 13 位 $h$。')
|
||
self.say('首次输出是状态右移十七位，因此输出的最低位，对应状态的第十七位。只需算状态低十八位，就能判断奇偶。', 12)
|
||
self.clear_body()
|
||
self.page('只在计算末尾取模，逐格检查偶数条件', [
|
||
(r'[A((p+d_i)\mathbin{\mathrm{xor}}C)+11]\bmod2^{18}<2^{17}', MINT),
|
||
(r'0\le p<2^{18}=262144', CYAN),
|
||
], [('加法、乘法与 XOR 的高位不会反过来影响低 18 位', INK),
|
||
('有一格失败：排除整个 p；全部通过：保存为根', AMBER),
|
||
('每根仍有 131072 种中间位；模 5 条件尚未检查', MUTED)])
|
||
self.say('先做完整整数运算，末尾统一保留低十八位。没有必要对加法输入和异或常量分别取模。', 10)
|
||
self.say('结果小于二的十七次方，说明第十七位为零。枚举全部 p，有一格失败就排除它，全部通过才保存为根。', 12)
|
||
self.say('这一轮只保证首次输出都是偶数。不同位置的根数不同，不能假设每增加一格就恰好减半。', 10)
|
||
self.clear_body()
|
||
d = DATA['ROOT']
|
||
self.page('已知 5×5 窗口的低位候选数量', [
|
||
(rf'262144\longrightarrow {d["roots"]}\ \mathrm{{roots}}', MINT),
|
||
(rf'{d["roots"]}\times131072={d["lower35"]}', CYAN),
|
||
], [('锚点 (51069,419124)，全部 25 格要求为史莱姆区块', INK),
|
||
('84 是这个窗口的实测结果，不是固定根数', MUTED)], kind='measurement')
|
||
self.say('这个已知窗口留下八十四个根。每根再补全部中间位，一共仍有一千一百零一万零四十八种低三十五位。', 12)
|
||
|
||
self.clear_body()
|
||
self.page('贯穿案例：沿其中的根 p = 218767 继续', [
|
||
(r'p=218767', CYAN),
|
||
(r'v_0\bmod2^{18}=59524<131072', INK),
|
||
(r'v_1\bmod2^{18}=80305<131072', MINT),
|
||
], [('其余 23 格也通过奇偶条件；m、h 仍未知', AMBER)], kind='example')
|
||
self.say('八十四个根中，我们跟随二十一万八千七百六十七。前两格的低位结果都小于二的十七次方，其余格子也通过。', 12)
|
||
|
||
def class_roots(self):
|
||
self.chapter('09', '复用筛选结果：同一坐标类只生成一次根', '本章输出：有根位置与 p 的任务；每张 GPU 使用有限缓存')
|
||
self.page('先展开相对坐标项的低 18 位', [
|
||
(r'd_i=F(x+\alpha_i)-F(x)+G(z+\beta_i)-G(z)\pmod{2^{48}}', CYAN),
|
||
(r'd_i\equiv4987142(2x\alpha_i+\alpha_i^2)+5947611\alpha_i', INK),
|
||
(r'\qquad+4392871(2z\beta_i+\beta_i^2)+389711\beta_i\pmod{2^{18}}', INK),
|
||
], [('αᵢ、βᵢ 是第 i 格相对锚点的坐标偏移', MUTED),
|
||
('Java 回绕与符号扩展不会改变这里的低 18 位', MINT)])
|
||
self.say('相对坐标项是两格坐标项的差。只看低十八位时，可以展开原来的二次多项式。', 10)
|
||
self.say('注意与锚点位置相关的项：横轴系数是二乘四百九十八万七千一百四十二，纵轴系数是二乘四百三十九万二千八百七十一。', 13)
|
||
self.clear_body()
|
||
self.page('移动一个周期，相对项变化为 2¹⁸ 的倍数', [
|
||
(r'x\mapsto x+2^{16}:\quad \Delta d_i=2\cdot4987142\cdot2^{16}\alpha_i', CYAN),
|
||
(r'z\mapsto z+2^{17}:\quad \Delta d_i=2\cdot4392871\cdot2^{17}\beta_i', MINT),
|
||
(r'\mathrm{class}(x,z)=(x\bmod65536,\ z\bmod131072)', INK),
|
||
], [('横轴系数 4987142 是偶数，多提供一个因子 2', AMBER),
|
||
('同类位置的相对项低 18 位相同，完整根列表相同', MINT)])
|
||
self.say('横轴系数是偶数，加上前面的二，所以移动二的十六次方，相对项就改变二的十八次方的整数倍。', 11)
|
||
self.say('纵轴移动二的十七次方，也得到同样的整倍数变化。因此用这两个坐标余数分类，同类可以共享完整根列表。', 12)
|
||
self.clear_body()
|
||
self.page('先复用根，再展开具体位置', notes=[
|
||
('位置归类 → 查缓存；未缓存的类才筛根', CYAN),
|
||
('无根类直接跳过；有根类展开具体位置与根', MINT),
|
||
('只共享低位条件，完整相对项和高位约束仍按位置计算', AMBER),
|
||
('根 p 是有效种子的低位，世界种子还要减回锚点项', MUTED)])
|
||
self.say('缓存省的是重复筛根。无根类直接跳过，有根类才展开具体位置。共享根不代表最终世界种子相同。', 11)
|
||
self.clear_body()
|
||
self.page('贯穿案例：这个窗口属于哪个坐标类', [
|
||
(r'(51069\bmod65536,\ 419124\bmod131072)=(51069,25908)', CYAN),
|
||
(r'\mathrm{cached\ roots}:\quad84', MINT),
|
||
], [('同类位置复用这 84 个根；完整高位约束仍需各自求解', INK),
|
||
('单个窗口不测缓存复用收益；范围任务取决于类的重复率', MUTED)], kind='example')
|
||
self.say('这个窗口的类键为五万一千零六十九、二万五千九百零八。同类位置可以复用相同的八十四个根。', 11)
|
||
self.say('缓存减少重复筛根，不减少当前窗口的根。单窗口无法测量跨位置的复用收益，因此这里不混入另一个批次的测速。', 12)
|
||
|
||
def prepare(self):
|
||
self.chapter('10', '每个根预计算一次，避免中间位循环重复计算', '本章输出：公共项 γᵢ、ωᵢ；E 是固定 XOR 常量的高位部分')
|
||
self.page('固定根，暂取 h = 0，定义基准输出', [
|
||
(r'\ell=p+2^{18}m,\qquad \bar q_i=q_i(0)', CYAN),
|
||
(r'\sigma_i=p+d_i=\eta_i+2^{18}\gamma_i', INK),
|
||
(r'\eta_i=\sigma_i\bmod2^{18},\quad \gamma_i=\lfloor\sigma_i/2^{18}\rfloor', MINT),
|
||
(r'\ell+d_i=\eta_i+2^{18}(\gamma_i+m)', INK),
|
||
], [('横线表示 h = 0 的基准输出，不表示平均值', MUTED)])
|
||
self.say('先暂时取高位 h 为零，把这个输出记为 q 上面加横线。横线表示基准值，不表示平均值。', 10,
|
||
display=r'暂取 $h=0$，定义基准输出 $\bar q_i=q_i(0)$；横线不表示平均值。')
|
||
self.say('根加相对项得到 sigma。拆成低十八位 eta，以及剩余部分 gamma。加入 m 后，只有高位部分变成 gamma 加 m。', 12,
|
||
display=r'$\sigma_i=p+d_i=\eta_i+2^{18}\gamma_i$；加入 $m$ 后，高位变成 $\gamma_i+m$。')
|
||
self.clear_body()
|
||
self.page('低位和高位分别 XOR，固定贡献只算一次', [
|
||
(r'E=C\gg18=\mathtt{0x1790d}', CYAN),
|
||
(r'\omega_i=\left\lfloor\frac{A(\eta_i\mathbin{\mathrm{xor}}(C\bmod2^{18}))+11}{2^{17}}\right\rfloor', INK),
|
||
(r'\bar q_i(m)=[\omega_i+2A((\gamma_i+m)\mathbin{\mathrm{xor}}E)]\bmod2^{31}', MINT),
|
||
], [('γᵢ：根加相对项后的高位；ωᵢ：低位推进贡献', CYAN),
|
||
('位置与根固定后，γᵢ、ωᵢ 均不随 m 改变', AMBER)])
|
||
self.say('把初始化常量的高位部分记为大写 E。低十八位推进产生的固定输出贡献记为 omega。', 10,
|
||
display=r'固定常量 $E=C\gg18$；低位推进的贡献记为 $\omega_i$。')
|
||
self.say('剩下的输入项乘 A 后右移十七位，二的十八次方变成系数二，得到下面的基准输出公式。', 11)
|
||
self.say('每个位置与根只准备一次 gamma 和 omega。后续把 m 代入，还能用三十二位整数计算最终回绕。', 11,
|
||
display=r'每个位置与根只准备一次 $\gamma_i,\omega_i$，随后代入 $m$。')
|
||
self.clear_body()
|
||
self.page('贯穿案例：前两格的公共项', [
|
||
(r'\begin{array}{c|r|r|r}i&\eta_i&\gamma_i&\omega_i\\\hline0&218767&0&46624833586\\1&128076&9848&13419656886\end{array}', INK),
|
||
(r'\bar q_0(40302)=227860608,\quad\bar q_1(40302)=1920935636', MINT),
|
||
], [('根仍为 218767；m = 40302 是后面筛出的成功分支', CYAN),
|
||
('ωᵢ 是中间贡献，可以大于 31 位；最终输出才取模', MUTED)], kind='example')
|
||
self.say('这个根的前两格公共项如表。把后来筛出的中间位四万零三百零二代入，就得到这两个基准输出。', 12)
|
||
self.measured_effect('P', '同一个 5×5 窗口：公共项预计算')
|
||
self.say('同窗口搜索从零点三二三五八四毫秒降到零点二六八二八八毫秒，约快一点二一倍。含每轮公共项准备，不含筛根和传输。', 14)
|
||
|
||
def group_filter(self):
|
||
self.chapter('11', '中间位：输出差早筛与 16 候选掩码', 'DOCUMENT.md 第 9、10、12 节 · 固定位置与 p，先不枚举 h')
|
||
self.page('未知高位不进入 XOR 翻转的低 35 位', [
|
||
(r'(\ell+d_i)\bmod2^{48}=\lambda_i+2^{35}\kappa_i,\quad C<2^{35}', CYAN),
|
||
(r'u_i(h)\equiv u_i(0)+2^{35}h\pmod{2^{48}}', INK),
|
||
(r'v_i(h)=(Au_i(0)+11+Ah\,2^{35})\bmod2^{48}', MINT),
|
||
(r'v_i(0)=(Au_i(0)+11)\bmod2^{48}', INK),
|
||
], [('κᵢ 已包含坐标加法的进位；11 已包含在基准状态 vᵢ(0) 中', AMBER)])
|
||
self.say('坐标进位已经包含在 kappa 中。C 只翻转低三十五位，因此高位 h 给初始状态增加二的三十五次方乘 h。', 12)
|
||
self.say('再乘 A 加十一。十一没有消失，它已经包含在基准状态 v 下标 i 的零参数里，所以新增量只有 A 乘 h 乘二的三十五次方。', 14)
|
||
self.clear_body()
|
||
self.page('共同平移在输出差中抵消', [
|
||
(r'q_i(h)=(\bar q_i+Ah\,2^{18})\bmod2^{31}', CYAN),
|
||
(r'\delta_i=(\bar q_i-\bar q_0)\bmod2^{31}', MINT),
|
||
(r'(q_i(h)-q_0(h))\bmod2^{31}=\delta_i', INK),
|
||
(r'2^{31}\bmod10=8,\quad\delta_i\bmod10\in\{0,8\}', AMBER),
|
||
], [('位置、p、m 固定后，δᵢ 与 h 无关；通过仍只是必要条件', MUTED)])
|
||
self.say('取高三十一位后，各格输出加上同一个量。相减可以消掉未知高位，所以先检查输出差。', 11)
|
||
self.say('两个输出都被十整除，直接差也被十整除。负差取模要加二的三十一次方，故模差只能除以十余零或八。', 12)
|
||
self.clear_body()
|
||
self.page('贯穿案例：两格输出与模差', [
|
||
(r'p=218767,\quad m=40302,\quad h=2995', CYAN),
|
||
(r'Ah\,2^{18}\bmod2^{31}=886833152', INK),
|
||
(r'q_0=1114693760,\quad q_1=660285140', MINT),
|
||
(r'q_1-q_0=-454408620,\quad\delta_1=1693075028', INK),
|
||
], [('δ₁ 除以 10 余 8；由基准输出相减得到完全相同的值', AMBER),
|
||
('这里先展示成功分支；高位如何得到，下一章展开', MUTED)], kind='example')
|
||
self.say('这个窗口的成功分支给两格相同的平移。右邻格先回绕，直接差为负四亿五千四百四十万八千六百二十。', 12)
|
||
self.say('取模后是十六亿九千三百零七万五千零二十八，除以十余八。直接用基准输出相减也得到同一结果。', 12)
|
||
self.clear_body()
|
||
self.page('16 候选成组：只改变 E 不翻转的四个位', [
|
||
(r'E=\mathtt{0x1790d},\quad\operatorname{bits}_{4:7}(E)=0000', AMBER),
|
||
(r'm_j=\mathrm{base}+16j,\quad0\le j<16', MINT),
|
||
(r'\mathrm{base}=256\lfloor g/16\rfloor+(g\bmod16),\quad0\le g<8192', CYAN),
|
||
], [('同一段：γᵢ + mⱼ 没跨过 256 的整数倍', INK),
|
||
('加 16 只改变第 4～7 位，因此 XOR 后也加 16', MINT)])
|
||
self.say('E 的第四到第七位为零。让中间位只改变这四位，得到间隔十六的一组十六个候选，总共八千一百九十二组。', 13)
|
||
self.say('同一段是指当前格的 gamma 加 m 没跨过二百五十六的整数倍。这时加十六只改变那四位，异或后也增加十六。', 13)
|
||
self.clear_body()
|
||
self.page('同步增加，模输出差保持不变', [
|
||
(r'\bar q_i(m_{j+1})\equiv\bar q_i(m_j)+32A\pmod{2^{31}}', CYAN),
|
||
(r'\bar q_0(m_{j+1})\equiv\bar q_0(m_j)+32A\pmod{2^{31}}', INK),
|
||
(r'\delta_i(m_{j+1})\equiv(\bar q_i+32A)-(\bar q_0+32A)', MINT),
|
||
(r'\qquad\equiv\delta_i(m_j)\pmod{2^{31}}', MINT),
|
||
], [('锚点 γ₀ = 0，整组不跨界；当前格在同一段内不跨界', MUTED),
|
||
('整组跨度 240 < 256，每格最多跨界一次，最多两段', AMBER)])
|
||
self.say('异或后每增加十六，输出增加三十二 A。锚点也增加同一个量，相减后增量抵消，同一段的模输出差完全相同。', 14)
|
||
self.say('跨界时进位进入可能被异或翻转的高位，差值可能切换。之后又保持不变。一组跨度只有二百四十，因此最多两段。', 13)
|
||
self.clear_body()
|
||
self.page('贯穿案例：选中包含 m = 40302 的组', [
|
||
(r'\mathrm{base}=40206,\quad\gamma_1=9848,\quad E=96525', CYAN),
|
||
(r'm_j=40206+16j,\quad j=0,\ldots,15', MINT),
|
||
(r'\begin{array}{r|r|r|r|r|r}j&m_j&\gamma_1+m_j&m_j\mathbin{\mathrm{xor}}E&(\gamma_1+m_j)\mathbin{\mathrm{xor}}E&\mathrm{diff}\\\hline0&40206&50054&123907&113291&-10616\\1&40222&50070&123923&113307&-10616\\7&40318&50166&124019&113403&-10616\\8&40334&50182&124035&113931&-10104\\15&40446&50294&124147&114043&-10104\end{array}', INK),
|
||
], [('j = 7 → 8：右邻格输入跨过 50176，这是 256 的整数倍', AMBER)], kind='example')
|
||
self.say('仍是这个窗口和这个根。组首为四万零二百零六，右邻格 gamma 为九千八百四十八。前八个候选的输入差都是负一万零六百一十六。', 14)
|
||
self.say('从七号到八号候选，右邻格输入跨过五万零一百七十六，异或后的输入差变成负一万零一百零四。后半组又保持相同。', 14)
|
||
self.clear_body()
|
||
self.page('贯穿案例：输入差变成真正的输出差', [
|
||
(r'\delta_1=\begin{cases}1693075028,&j=0,\ldots,7,\\411302484,&j=8,\ldots,15.\end{cases}', MINT),
|
||
(r'\delta_1=(\omega_1-\omega_0+2A\cdot\mathrm{input\ difference})\bmod2^{31}', INK),
|
||
], [('前段余 8：保留 j = 0～7；后段余 4：整段排除', AMBER),
|
||
('右邻格的允许掩码为 0x00ff', CYAN)], kind='example')
|
||
self.say('输入差还要乘二 A，加上公共项之差，再取模，才是输出差。前段余八、后段余四，因此一次保留前八个、排除后八个。', 14)
|
||
self.clear_body()
|
||
self.page('贯穿案例：全部 25 格的允许掩码求交', [
|
||
(r'\begin{array}{c|c|c}i&\mathrm{allowed\ mask}&\mathrm{remaining}\ j\\\hline1&\mathtt{00ff}&0\ldots7\\3&\mathtt{fffc}&2\ldots7\\4&\mathtt{fff8}&3\ldots7\\8&\mathtt{fff0}&4\ldots7\\9&\mathtt{ffc0}&6,7\end{array}', INK),
|
||
(r'\mathrm{final\ mask}=\mathtt{00c0}\quad\Longrightarrow\quad m=40302,40318', MINT),
|
||
], [('表中略去的格子也参与检查，但不再缩小累计交集', MUTED),
|
||
('只对幸存中间位求高位；下一章先沿 40302 继续', AMBER)], kind='example')
|
||
self.say('所有格子的掩码按位求交，逐步缩小到六号、七号候选。检查完全部二十五格，留下中间位四万零三百零二和四万零三百一十八。', 14)
|
||
self.clear_body()
|
||
self.page('同窗口的候选数量与成组筛选效果', [
|
||
(r'11010048\ \mathrm{lower35}\longrightarrow36\ \mathrm{survivors}', CYAN),
|
||
(r'0.268288\ \mathrm{ms}\longrightarrow0.156672\ \mathrm{ms}', MINT),
|
||
], [('预计算后再增加组 mask：约 1.71×；两项合计约 2.07×', AMBER),
|
||
('搜索 CUDA event 中位数；含公共项准备，不含筛根与传输', MUTED)], kind='measurement')
|
||
self.say('全部八十四个根展开后，输出差过滤留下三十六种低三十五位。同窗口成组筛选再快约一点七一倍，与预计算合计约二点零七倍。', 14)
|
||
|
||
def upper(self):
|
||
self.chapter('12', '高位：用 θ 区间求交恢复 h', 'DOCUMENT.md 第 13 节 · 不逐个尝试 8192 种高位')
|
||
self.page('拆分基准输出，高位换元为 θ', [
|
||
(r'\bar q_i=r_i+2^{18}b_i,\quad0\le b_i<8192', CYAN),
|
||
(r'\theta=Ah\bmod8192,\qquad h=4965\theta\bmod8192', MINT),
|
||
(r'\phi_i=(b_i+\theta)\bmod8192,\quad q_i(h)=r_i+2^{18}\phi_i', INK),
|
||
], [('A mod 8192 = 1645，1645 × 4965 mod 8192 = 1', MUTED),
|
||
('rᵢ、bᵢ 已知，θ 未知；换元不重不漏', AMBER)])
|
||
self.say('把基准输出拆成低十八位 r 和高十三位 b。令 theta 等于 A 乘 h 模八千一百九十二，再用模逆恢复 h。', 12,
|
||
display=r'$\theta=Ah\bmod8192$，由 $h=4965\theta\bmod8192$ 恢复高位。')
|
||
self.clear_body()
|
||
self.page('单格变成两段区间与模 5 条件', [
|
||
(r'2^{18}\equiv-1\pmod5,\quad q_i\equiv r_i-\phi_i\pmod5', CYAN),
|
||
(r'\tau_i=8192-b_i', INK),
|
||
(r'\begin{array}{c|c}\theta\text{ interval}&\text{required residue mod }5\\\hline[0,\tau_i)&r_i-b_i\\{}[\tau_i,8192)&r_i-b_i+2\end{array}', MINT),
|
||
], [('低位筛选已保证偶数；这里只需补模 5 条件', AMBER),
|
||
('多出的 2 来自 8192 mod 5 = 2', MUTED)])
|
||
self.say('奇偶已经通过，只需再满足模五条件。二的十八次方除以五余负一，所以要求平移后的高位 phi 与 r 同余。', 12)
|
||
self.say('b 加 theta 最多回绕一次。回绕前要求一个余数，回绕后多出二，形成两段区间条件。', 11)
|
||
self.clear_body()
|
||
self.page('逐格求交，只枚举实际共同解', [
|
||
(r"[\mathrm{lo},\mathrm{hi})\cap[\mathrm{lo}',\mathrm{hi}')=[\max(\mathrm{lo},\mathrm{lo}'),\min(\mathrm{hi},\mathrm{hi}'))", INK),
|
||
(r'\theta_{\min}=\mathrm{lo}+((\rho-\mathrm{lo})\bmod5)', MINT),
|
||
(r'\theta_{\min},\theta_{\min}+5,\ldots<\mathrm{hi}', CYAN),
|
||
], [('余数不同就删除；区间内没有同余整数也删除', AMBER),
|
||
('每个既定余数最多匹配一段，始终最多保留两条', MUTED)])
|
||
self.say('相同余数的区间求交，不同余数直接删除。区间非空还不够，必须确实包含满足余数的整数。', 11)
|
||
self.say('每格对一个既定余数最多匹配一段，因此始终最多保留两条。最后按步长五枚举共同解，再恢复 h。', 12)
|
||
self.clear_body()
|
||
self.page('贯穿案例：固定 p = 218767、m = 40302', [
|
||
(r'\begin{array}{c|r|r|r|r}i&\bar q_i&r_i&b_i&\tau_i\\\hline0&227860608&57472&869&7323\\1&1920935636&206548&7327&865\end{array}', INK),
|
||
(r'i=0:\ [0,7323):\rho=3;\ [7323,8192):\rho=0', CYAN),
|
||
(r'i=1:\ [0,865):\rho=1;\ [865,8192):\rho=3', MINT),
|
||
], [('前两格共同留下 [865,7323)，要求 θ mod 5 = 3', AMBER)], kind='example')
|
||
self.say('还是同一条成功分支。前两格的 r、b 和回绕点都由基准输出算出。只有余三的两段能匹配，交集是八百六十五到七千三百二十三。', 14)
|
||
self.clear_body()
|
||
self.page('贯穿案例：继续加入其余格子', [
|
||
(r'\begin{array}{c|c|c}\text{through cell}&\text{interval}&\rho\\\hline1&[865,7323)&3\\2&[865,3544)&3\\3&[3202,3544)&3\\13&[3202,3506)&3\\19&[3382,3506)&3\\22&[3382,3440)&3\\24&[3382,3440)&3\end{array}', INK),
|
||
(r'\theta=3383,3388,\ldots,3438\quad(12\ \mathrm{solutions})', MINT),
|
||
], [('全部 25 格共同允许 [3382,3440) 中除以 5 余 3 的整数', AMBER)], kind='example')
|
||
self.say('逐格收紧后，整个窗口共同允许的区间是三千三百八十二到三千四百四十，余数为三。', 11)
|
||
self.say('第一个整数解是三千三百八十三，之后每次加五，直到三千四百三十八，共十二个高位解。', 11)
|
||
self.clear_body()
|
||
self.page('贯穿案例：恢复第一个完整世界种子', [
|
||
(r'\theta=3383\quad\Longrightarrow\quad h=4965\cdot3383\bmod8192=2995', CYAN),
|
||
(r's=218767+2^{18}\cdot40302+2^{35}\cdot2995=102917981558415', INK),
|
||
(r'w=(s-T_0)\bmod2^{48}=15959335054446', MINT),
|
||
], [('m = 40318 的另一条分支同样得到 12 个解，共 24 个', AMBER)], kind='example')
|
||
self.say('取第一个 theta 解，恢复 h 为二千九百九十五，拼回 s，再减去锚点项，得到世界种子十五万九千五百九十三亿三千五百零五万四千四百四十六。', 15,
|
||
display=r'$\theta=3383\Rightarrow h=2995\Rightarrow s=102917981558415\Rightarrow w=15959335054446$。')
|
||
self.measured_effect('D', '同窗口：输出差与区间求交的组合效果')
|
||
self.say('同窗口旧排序流程六十三点七五零毫秒，差过滤与区间求交组合约零点三二四毫秒，约快一百九十七倍。', 13)
|
||
self.say('这是组合效果，不是区间单项收益，也不包含筛根与传输。', 8)
|
||
|
||
def verify_output(self):
|
||
self.chapter('13', '完整验证：恢复的种子让全部 25 格通过', 'DOCUMENT.md 第 14 节 · 验证输出正确，覆盖边界另行说明')
|
||
self.page('贯穿案例：世界种子 15959335054446 的原始输出', [
|
||
(r'\begin{array}{rrrrr}1114693760&660285140&2105382940&47575410&1796905160\\2074383590&1410817530&1734889590&2009625200&440710690\\1664890290&537178720&1699969350&2115254790&688097620\\1842255790&1387847170&1302453480&1264531310&344660\\1757217670&204531470&2132545510&1606583470&569937090\end{array}', MINT),
|
||
], [('按窗口编号排列；每个输出都能被 10 整除', CYAN),
|
||
('全部小于 2147483640，不会拒绝；25 次 nextInt(10) 均返回 0', AMBER)], kind='example')
|
||
self.say('把恢复的世界种子代回最开始的代码，二十五格原始输出如表。每个数都被十整除，也都在接受范围内。', 12)
|
||
self.say('因此这个种子确实让整个五乘五成为史莱姆区块。其余二十三个种子也逐格执行完整 Java 判断。', 11)
|
||
self.clear_body()
|
||
self.page('完整验证与候选覆盖的边界', [
|
||
(r'q\ge2^{31}-8=2147483640\quad\Longrightarrow\quad\mathrm{redraw}', AMBER),
|
||
(r's=p+2^{18}m+2^{35}h,\quad w=(s-T_0)\bmod2^{48}', CYAN),
|
||
], [('实际流程先用 s、dᵢ 完整验证，通过后恢复并记录 w', MINT),
|
||
('拒绝后重抽可能改变结果，准确验证会排除误报', INK),
|
||
('依赖重抽才成立的种子可能未生成；验证不能补回遗漏', AMBER)])
|
||
self.say('Java 会拒绝最后八个原始输出并重抽。准确验证可以消除候选中的误报。', 10)
|
||
self.say('但依赖重抽才成功的种子，可能在首次输出候选阶段已被排除。所以当前算法保证输出正确，不保证完整覆盖所有 Java 解。', 13)
|
||
|
||
def execution(self):
|
||
self.chapter('14', 'GPU 执行：按位置与根供给任务，按组搜索', 'DOCUMENT.md 第 15 节 · 并行安排不改变数学条件')
|
||
self.page('当前入口的执行顺序', notes=[
|
||
('位置归类 → 查低位根缓存 → 未缓存类才筛根', CYAN),
|
||
('有根位置展开（位置、root）任务 → 每根准备公共项', INK),
|
||
('GPU 线程处理（位置、root、16 候选组）', MINT),
|
||
('mask 幸存者求高位 → 完整验证 → 恢复世界种子', AMBER),
|
||
('多卡动态领取位置批次，各自维护有限根缓存', MUTED)])
|
||
self.say('CPU 分批提供位置。GPU 先筛根、准备公共项，再让每个搜索线程负责一个位置、一个根和一组十六个中间位。', 13)
|
||
self.say('组内幸存者继续求高位并完整验证。多张卡动态领取位置批次，各自维护根缓存，最后合并结果。', 11)
|
||
|
||
def ending(self):
|
||
self.chapter('15', '整条流程：同一个窗口，每一步省下什么', 'DOCUMENT.md 第 16、17 节 · 符号与效果回顾')
|
||
self.page('贯穿案例的完整候选链', [
|
||
(r'262144\ \mathrm{low18}\longrightarrow84\ \mathrm{roots}', CYAN),
|
||
(r'84\cdot131072=11010048\ \mathrm{lower35}\longrightarrow36', MINT),
|
||
(r'm=40302,40318\quad\Longrightarrow\quad12+12=24\ \mathrm{seeds}', AMBER),
|
||
], [('36 个差过滤幸存者的根都为 p = 218767', INK),
|
||
('完整演算的一个结果：w = 15959335054446', CYAN)], kind='example')
|
||
self.say('同一个窗口，八十四个根展开中间位，差过滤留下三十六种低三十五位。只有两种中间位有高位解，各十二个，共二十四个世界种子。', 14)
|
||
self.clear_body()
|
||
self.page('符号：种子、基准输出与公共项', [
|
||
(r's=p+2^{18}m+2^{35}h,\quad w=(s-T_0)\bmod2^{48}', CYAN),
|
||
(r'\bar q_i=q_i(0),\quad\delta_i=(\bar q_i-\bar q_0)\bmod2^{31}', MINT),
|
||
(r'\bar q_i(m)=[\omega_i+2A((\gamma_i+m)\mathbin{\mathrm{xor}}E)]\bmod2^{31}', INK),
|
||
], [('p、m、h 属于种子；γᵢ、ωᵢ 每根准备一次', MUTED),
|
||
('δᵢ 随位置、p、m 变化，与 h 无关', AMBER)])
|
||
self.say('p、m、h 是有效种子的三段。横线表示基准输出，gamma 和 omega 是公共项。delta 是模输出差，与未知高位无关。', 13)
|
||
self.clear_body()
|
||
self.page('符号：高位换元与区间', [
|
||
(r'\bar q_i=r_i+2^{18}b_i,\quad\theta=Ah\bmod8192', CYAN),
|
||
(r'\phi_i=(b_i+\theta)\bmod8192', MINT),
|
||
(r'\theta\in[\mathrm{lo},\mathrm{hi}),\quad\theta\equiv\rho\pmod5', INK),
|
||
], [('T：坐标项；θ：种子高位的换元，二者含义不同', AMBER),
|
||
('rᵢ、bᵢ、φᵢ 属于输出；lo、hi 只表示区间端点', MUTED)])
|
||
self.say('大写 T 是坐标项，theta 是高位换元。r、b、phi 属于输出；lo、hi 是区间端点。符号在正文末尾有完整总表。', 13)
|
||
self.clear_body()
|
||
self.page('同窗口优化的实测效果', notes=[
|
||
('输出差＋区间求交：63.750 → 约 0.324 ms（197×）', CYAN),
|
||
('公共项预计算：0.323584 → 0.268288 ms（1.21×）', INK),
|
||
('成组 mask：0.268288 → 0.156672 ms（再快 1.71×）', MINT),
|
||
('后两项同轮对照合计 2.07×；不跨实验连乘倍数', AMBER),
|
||
('均为搜索阶段；不含筛根、初始化与传输', MUTED)], kind='measurement')
|
||
self.say('效果也使用同一个窗口。预计算减少重复算术，成组掩码共用差过滤，区间求交减少高位尝试。不同轮次的倍数不能连乘。', 14)
|
||
self.say('从 CPU 到 GPU，我们先并行和复用计算；理解 Random 后，再排除不可能的候选，并直接求出剩余高位。', 12)
|
||
|
||
def tear_down(self):
|
||
output = HERE / 'output'
|
||
output.mkdir(exist_ok=True)
|
||
name = self.__class__.__name__
|
||
(output / f'{name}.timeline.json').write_text(json.dumps(
|
||
{'duration': float(self.time), 'chapters': self.chapters, 'cues': self.cues}, ensure_ascii=False, indent=2)+'\n')
|
||
def stamp(t):
|
||
ms = round(t*1000)
|
||
return f'{ms//3600000:02}:{ms//60000%60:02}:{ms//1000%60:02},{ms%1000:03}'
|
||
(output / f'{name}.srt').write_text('\n\n'.join(
|
||
f'{i}\n{stamp(c["start"])} --> {stamp(c["end"])}\n{c["text"]}' for i,c in enumerate(self.cues,1))+'\n')
|
||
(output / f'{name}.narration.md').write_text('# 口播稿（与当前渲染时间轴一致）\n\n'+
|
||
'\n\n'.join(f'[{stamp(c["start"])}] {c["text"]}' for c in self.cues)+'\n')
|
||
super().tear_down()
|
||
|
||
|
||
class SlimeFilm(FilmBase):
|
||
def construct(self):
|
||
for part in (self.opening, self.problem, self.cuda, self.mapping, self.outer,
|
||
self.random_bridge, self.normalize, self.low_roots, self.class_roots,
|
||
self.prepare, self.group_filter, self.upper, self.verify_output,
|
||
self.execution, self.ending):
|
||
part()
|
||
|
||
|
||
class ParallelEpisode(FilmBase):
|
||
def construct(self):
|
||
for part in (self.opening, self.problem, self.cuda, self.mapping, self.outer):
|
||
part()
|
||
|
||
|
||
class RandomEpisode(FilmBase):
|
||
def construct(self):
|
||
for part in (self.random_bridge, self.normalize, self.low_roots, self.class_roots,
|
||
self.prepare, self.group_filter, self.upper, self.verify_output,
|
||
self.execution, self.ending):
|
||
part()
|