LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
gcdext.c
浏览该文件的文档.
1/**
2 * Copyright (C) 2026 HJimmyK (Jericho Knox)
3 *
4 * This file is part of LMMP.
5 *
6 * LMMP is free software: you can redistribute it and/or modify it
7 * under the terms of the GNU Lesser General Public License as
8 * published by the Free Software Foundation; either version 3 of
9 * the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library. If not, see
18 * <https://www.gnu.org/licenses/>.
19 *
20 * SPDX-License-Identifier: LGPL-3.0-or-later
21 */
22
23/*
24扩展欧几里得:hgcd 分治驱动 + 通用分发 + 模逆元。
25
26一、hgcd 驱动(lmmp_gcdext_hgcd_)
27
28值序归一化 U >= V 后全程维护精确恒等式
29
30 V = u0*a + u1*b
31
32其中 (a;b) 为当前归约数对(零填充公共长度表示),行元素 (u0,u1) 非负。
33记累积变换 (U;V) = M*(a;b),行即 M 的第 1 行,detsign = det(M) = [1|-1]。
34
35 - 初始归约:U 长于 V 时做一次除法 a = U mod V(商丢弃——除法矩阵
36 E_div = /q 1;1 0/ 的行 1 = (1,0) 不含 q,q 乘零行元素无需计算,共
37 因子信息无损,免旧实现的迭代预归约及其行乘开销;行取 (1,0)、
38 detsign = -1);整除则 g = V,系数 (0,1) 直接发射;
39 - 主循环(公共长度 n > HGCD_RECURSE_THRESHOLD):取 p = n/2(首轮,
40 行为单位行 (0,1) 或 (1,0),成功后直接取 M1 的第 1/0 行为行
41 ((0,1)*M1 = 行1、(1,0)*M1 = 行0),免一次行乘)或 p = n/3(后续轮),
42 对高位片 (a+p; b+p) 调 lmmp_hgcd_core_(hgcd.c 共享入口,零改动),
43 经 lmmp_hgcd_adjust_ 修补低位合入;行 <- 行*M1 经 gcdext_row_mul_
44 原位完成;
45 - 除法步(core 失败/修补被拒):先试一次减法 r = a - b——core 失败
46 多为近邻对(顶端过近),商为 1,减法 + 行纯加(gcdext_row_qscalar_
47 原位 addmul + 指针对调)即完成一步且免除法;r >= b(商 >= 2)时做
48 一次除法 a = q*b + r,商为标量走原位 addmul,多 limb 商走全乘。
49 余数为 0 即终态 (g;0);
50 - 尾段(n <= 阈值):转 lmmp_gcdext_lehmer_ 取当前对的极小系数
51 (sigma,tau),组合 S_raw = detsign*(sigma*u1 - tau*u0)(两次全乘),
52 极小化快测 2*g*|S| <= V(一次 sn*gn 乘 + 比较,多数直接通过,免算
53 D = V/g);未过时按 D 向 0 平移(S_raw 与真值同格类
54 S_true ≡ S_raw (mod V/g),至多偏离数步;平局恒取正——该侧配对系数
55 满足 |t| <= U/(2g),另一侧 |g + D*U/2| > D*U/2 必越界);
56 - (g;0) 终态(除法步整除):解间隔 u0 = V/g,候选 detsign*u1 + k*u0
57 取距 0 近者(平局恒取正候选,与 gcdext_lehmer.c 同一选点规则)。
58
59s 为 U(值序大者)的极小系数(单模变换保持极小性);t 不跟踪,输出相位
60按 t = (g - s*A)/B(A/B 为值序大/小原对)经 lmmp_divexact_(B 偶时剥
612^k)导出(lmmp_gcdext_derive_/lmmp_gcdext_emit_,与 lehmer 层经
62impl/gcd.h 共享),dstt==NULL 时跳过(modinv 路径)。
63
64矩阵元素全程 <= max(U,V)(收敛子界),行缓冲 n0+2 覆盖;行乘产品经
65hgcd scratch 池(写长可达 u0n+M1 元素长,和归一化后 <= n0+1)。
66
67二、分发(lmmp_gcdext_)
68
69v==1 转 lmmp_gcdext_1_、vn==2(un>2)转 lmmp_gcdext_2_;两侧均超
70GCD_HGCD_THRESHOLD 转 hgcd 驱动(不满足时初始归约后公共长不足,hgcd
71无递归空间,Lehmer 更优),否则 lmmp_gcdext_lehmer_。
72
73三、模逆元(lmmp_modinv_ulong_ / lmmp_modinv_)
74
75经 gcdext 的 dstt=NULL 路径(全程不计算 t 侧),s<0 时逆元 = m-|s|。
76*/
77
78#include "numth/gcd.h"
79#include "impl/inlines.h"
80#include "impl/longlong.h"
81#include "mparam.h"
82#include "impl/tmp_alloc.h"
83#include "lmmp/lmmpn.h"
84#include "lmmp/numth.h"
85
86
87/* ---------------- 行向量原位更新 ---------------- */
88
89/*
90行除法步原位更新(q >= 1 标量):(u0,u1) <- (q*u0 + u1, u0)。
91u1 += q*u0 经补零 + addmul_1 原位完成,随后 u0/u1 指针对调(新 u0 落在
92原 u1 槽);u0 == 0 时纯对调。u1 槽容量 >= max(u0n,u1n)+1(行槽 n0+2 覆盖)
93*/
94static void gcdext_row_qscalar_(mp_ptr* u0p, mp_ptr* u1p, mp_size_t* u0n, mp_size_t* u1n,
95 ulong q) {
96 if (*u0n == 0) {
97 LMMP_SWAP(*u0p, *u1p, mp_ptr);
98 LMMP_SWAP(*u0n, *u1n, mp_size_t);
99 return;
100 }
101 if (*u1n < *u0n)
102 lmmp_zero(*u1p + *u1n, *u0n - *u1n);
103 mp_limb_t cy = lmmp_addmul_1_(*u1p, *u0p, *u0n, q);
104 mp_size_t un = *u0n > *u1n ? *u0n : *u1n;
105 if (*u1n > *u0n && cy != 0) {
106 /* u1 更长:进位属于 u0n 处,须经 u1 既有高位 [u0n,u1n) 传播后再入顶 */
107 cy = lmmp_add_1_(*u1p + *u0n, *u1p + *u0n, *u1n - *u0n, cy);
108 }
109 (*u1p)[un] = cy;
110 un += (cy != 0);
111 while (un > 1 && (*u1p)[un - 1] == 0)
112 --un;
113 LMMP_SWAP(*u0p, *u1p, mp_ptr);
114 *u1n = *u0n;
115 *u0n = un;
116}
117
118/*
119行矩阵步原位更新:
120 (u0,u1) <- (u0,u1)*M1,即 u0' = u0*m00 + u1*m10、u1' = u0*m01 + u1*m11
121全部元素非负(驱动行与 M1 均非负,无符号分支)。t0 <- u0 副本后:
122u0' 的 m10 项直写 u0 槽、m00 项入 t1 相加;u1' 的 m11 项先入 t1(u1 尚
123存活),m01 项覆写 u1 槽后相加——4 乘 2 加 1 拷贝,无中间行拷贝。
124产品按写长(含高位零)整段相加,末端一次归一化。t0/t1 容量
125max(u0n,u1n)+maxlen(M1)+2;行槽容量 n0+2 覆盖(各项非负,单项 <= 和 <=
126收敛子界 n0+1)
127*/
128static void gcdext_row_mul_(mp_ptr u0p, mp_ptr u1p, mp_size_t* u0n, mp_size_t* u1n,
130 mp_size_t un0 = *u0n, un1 = *u1n;
131 mp_size_t mark = sc->used;
132 mp_size_t sz = (un0 > un1 ? un0 : un1) + lmmp_gcd_matrix_maxlen_(M1) + 2;
133 mp_ptr t0 = lmmp_hgcd_salloc_(sc, sz);
134 mp_ptr t1 = lmmp_hgcd_salloc_(sc, sz);
135 lmmp_copy(t0, u0p, un0);
136
137 /* u0' = t0*m00 + u1*m10 -> u0p */
138 mp_size_t l0 = 0, l1 = 0;
139 if (un0 != 0 && M1->n[0][0] != 0) {
140 lmmp_gcd_mul_(t1, t0, un0, M1->m[0][0], M1->n[0][0]);
141 l0 = un0 + M1->n[0][0];
142 }
143 if (un1 != 0 && M1->n[1][0] != 0) {
144 lmmp_gcd_mul_(u0p, u1p, un1, M1->m[1][0], M1->n[1][0]);
145 l1 = un1 + M1->n[1][0];
146 }
147 mp_size_t n0n;
148 if (l0 != 0 && l1 != 0) {
149 mp_limb_t c = (l1 >= l0) ? lmmp_add_(u0p, u0p, l1, t1, l0) : lmmp_add_(u0p, t1, l0, u0p, l1);
150 n0n = l1 > l0 ? l1 : l0;
151 if (c != 0)
152 u0p[n0n++] = c;
153 } else if (l0 != 0) {
154 lmmp_copy(u0p, t1, l0);
155 n0n = l0;
156 } else {
157 n0n = l1; /* 两项皆零即新 u0 为零 */
158 }
159 while (n0n > 1 && u0p[n0n - 1] == 0)
160 --n0n;
161
162 /* u1' = u1*m11 + t0*m01 -> u1p(m11 项先入 t1,u1 覆写后相加) */
163 mp_size_t l2 = 0, l3 = 0;
164 if (un1 != 0 && M1->n[1][1] != 0) {
165 lmmp_gcd_mul_(t1, u1p, un1, M1->m[1][1], M1->n[1][1]);
166 l2 = un1 + M1->n[1][1];
167 }
168 if (un0 != 0 && M1->n[0][1] != 0) {
169 lmmp_gcd_mul_(u1p, t0, un0, M1->m[0][1], M1->n[0][1]);
170 l3 = un0 + M1->n[0][1];
171 }
172 mp_size_t n1n;
173 if (l2 != 0 && l3 != 0) {
174 mp_limb_t c = (l3 >= l2) ? lmmp_add_(u1p, u1p, l3, t1, l2) : lmmp_add_(u1p, t1, l2, u1p, l3);
175 n1n = l2 > l3 ? l2 : l3;
176 if (c != 0)
177 u1p[n1n++] = c;
178 } else if (l2 != 0) {
179 lmmp_copy(u1p, t1, l2);
180 n1n = l2;
181 } else {
182 n1n = l3;
183 }
184 while (n1n > 1 && u1p[n1n - 1] == 0)
185 --n1n;
186
187 *u0n = n0n;
188 *u1n = n1n;
189 sc->used = mark;
190}
191
192/*
193(g;0) 终态选点:解间隔 u0 = V/g,候选 detsign*u1 + k*u0 取距 0 近者
194(平局恒取 +u1:该侧配对系数满足界,另一侧 |g+u1*U| > u1*U 必越界)。
195幅度写入 sp(容量 >= u0n),符号 *sneg;t1 为 2*u1 暂存(容量 >= u1n+1)
196*/
197static mp_size_t gcdext_pick_s_(mp_ptr sp, int* sneg, mp_srcptr u0p, mp_size_t u0n,
198 mp_srcptr u1p, mp_size_t u1n, int det, mp_ptr t1) {
199 if (u1n == 0) {
200 *sneg = 0;
201 return 0;
202 }
203 mp_limb_t c2 = lmmp_mul_1_(t1, u1p, u1n, 2);
204 mp_size_t twon = u1n + (c2 != 0);
205 int cmp2;
206 if (twon != u0n) {
207 cmp2 = twon < u0n ? -1 : 1;
208 } else {
209 cmp2 = lmmp_cmp_(t1, u0p, u0n);
210 }
211 if (cmp2 <= 0) {
212 lmmp_copy(sp, u1p, u1n);
213 *sneg = cmp2 == 0 ? 0 : det < 0;
214 return u1n;
215 }
216 /* S = detsign*(u1-u0):幅度 u0-u1(u1 < u0;u1==u0 时 det 强制皆 1,幅度 0) */
217 lmmp_sub_(sp, u0p, u0n, u1p, u1n);
218 mp_size_t rn = u0n;
219 while (rn > 0 && sp[rn - 1] == 0)
220 --rn;
221 *sneg = (det > 0 && rn != 0);
222 return rn;
223}
224
226 mp_size_t sn, int sneg, mp_srcptr xp, mp_size_t xn, mp_srcptr yp,
227 mp_size_t yn, mp_ptr nb, mp_ptr yt, mp_ptr qt) {
228 if (sn == 0) {
229 dst[0] = 1; /* g == Y */
230 *tneg = 0;
231 return 1;
232 }
233 /* P = |S|*X(P >= X >= g,写长 sn+xn) */
234 if (sn >= xn)
235 lmmp_mul_(nb, sp, sn, xp, xn);
236 else
237 lmmp_mul_(nb, xp, xn, sp, sn);
238 mp_size_t pn = sn + xn;
239 while (pn > 0 && nb[pn - 1] == 0)
240 --pn;
241 lmmp_debug_assert(pn > 0);
242 /* N = |g - S*X| */
243 if (sneg) {
244 mp_limb_t c = lmmp_add_(nb, nb, pn, gp, gn);
245 if (c != 0)
246 nb[pn++] = c;
247 *tneg = 0;
248 } else {
249 mp_limb_t bw = lmmp_sub_(nb, nb, pn, gp, gn);
250 lmmp_debug_assert(bw == 0);
251 while (pn > 0 && nb[pn - 1] == 0)
252 --pn;
253 *tneg = pn != 0;
254 }
255 if (pn == 0) {
256 /* 理论不可达:N==0 ⟺ |S|*X == g,仅 X==g 且 |S|==1,即入口 U==V(已早退) */
257 dst[0] = 0;
258 *tneg = 0;
259 return 0;
260 }
261 /* 剥 Y 的 2^k(Y 归一化故 j 扫描必终止) */
262 mp_size_t j = 0;
263 while (yp[j] == 0)
264 ++j;
265 ulong y0; /* 仅需 cnt,奇化值不使用 */
266 int sb;
267 ctz_shr_u64(y0, yp[j], sb);
268 (void)y0;
269 /* N >>= k(整 limb 段 j + 位段 sb,低位必为零) */
270 mp_ptr np = nb + j;
271 mp_size_t nn = pn - j;
272 if (sb != 0) {
273 mp_limb_t out = lmmp_shr_(np, np, nn, sb);
274 lmmp_debug_assert(out == 0);
275 while (nn > 0 && np[nn - 1] == 0)
276 --nn;
277 }
278 /* Y >>= k 奇化到 yt(归一化) */
279 mp_size_t yn2 = yn - j;
280 if (sb != 0) {
281 lmmp_shr_(yt, yp + j, yn2, sb);
282 while (yn2 > 0 && yt[yn2 - 1] == 0)
283 --yn2;
284 } else {
285 lmmp_copy(yt, yp + j, yn2);
286 }
287 lmmp_debug_assert(yn2 > 0 && (yt[0] & 1) == 1);
288 lmmp_debug_assert(nn >= yn2);
289 /*
290 tv = N/Y(|tv| >= 1 故 nn >= yn2)。lmmp_divexact_ 的写入长为 nn-yn2+1
291 (顶 limb 可为零),可能超出 dst 的公开容量契约(值 |tv| <= X/(2g) <=
292 xn limb,但写长至 xn+1)——先整商落内部暂存 qt,再按归一化 rn 拷出
293 */
294 lmmp_divexact_(qt, np, nn, yt, yn2);
295 mp_size_t rn = nn - yn2 + 1;
296 while (rn > 0 && qt[rn - 1] == 0)
297 --rn;
298 lmmp_debug_assert(rn > 0);
299 lmmp_copy(dst, qt, rn);
300 return rn;
301}
302
304 mp_srcptr gp, mp_size_t gn, mp_srcptr sp, mp_size_t sun, int suneg, int sw,
305 mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn, mp_ptr nb, mp_ptr yt,
306 mp_ptr qt) {
307 if (!sw) {
308 /* s = S(up 为大者),t = (g - S*up)/vp */
309 if (dstt != NULL) {
310 int tneg;
311 mp_size_t rn = lmmp_gcdext_derive_(dstt, &tneg, gp, gn, sp, sun, suneg, up, un, vp, vn,
312 nb, yt, qt);
313 if (rn == 0)
314 dstt[0] = 0;
315 *tn = (rn != 0 && tneg) ? -(mp_ssize_t)rn : (mp_ssize_t)rn;
316 }
317 lmmp_copy(dstg, gp, gn);
318 lmmp_copy(dsts, sp, sun);
319 if (sun == 0)
320 dsts[0] = 0;
321 *sn = (sun != 0 && suneg) ? -(mp_ssize_t)sun : (mp_ssize_t)sun;
322 } else {
323 /* t = S(vp 为大者),s = (g - S*vp)/up(导出 X 用值序大者 up) */
324 int tneg;
325 mp_size_t rn = lmmp_gcdext_derive_(dsts, &tneg, gp, gn, sp, sun, suneg, up, un, vp, vn, nb,
326 yt, qt);
327 lmmp_copy(dstg, gp, gn);
328 if (dstt != NULL) {
329 lmmp_copy(dstt, sp, sun);
330 if (sun == 0)
331 dstt[0] = 0;
332 *tn = (sun != 0 && suneg) ? -(mp_ssize_t)sun : (mp_ssize_t)sun;
333 }
334 if (rn == 0)
335 dsts[0] = 0;
336 *sn = (rn != 0 && tneg) ? -(mp_ssize_t)rn : (mp_ssize_t)rn;
337 }
338}
339
340/* ---------------- hgcd 分治驱动 ---------------- */
341
343
345 mp_ssize_t* tn, mp_srcptr up, mp_size_t un, mp_srcptr vp,
346 mp_size_t vn) {
347 lmmp_param_assert(un > 0 && vn > 0);
348 lmmp_param_assert(up != NULL && vp != NULL && dstg != NULL && dsts != NULL && sn != NULL);
349 lmmp_param_assert(up[un - 1] != 0 && vp[vn - 1] != 0);
350
351 /* 值序归一化(sw 记录交换;s 恒为原始 up 的系数) */
352 int sw = 0;
353 if (un < vn) {
354 LMMP_SWAP(up, vp, mp_srcptr);
355 LMMP_SWAP(un, vn, mp_size_t);
356 sw = 1;
357 } else if (un == vn) {
358 int c = lmmp_cmp_(up, vp, un);
359 if (c == 0) {
360 lmmp_copy(dstg, up, un);
361 dsts[0] = 0;
362 *sn = 0;
363 if (dstt != NULL) {
364 dstt[0] = 1;
365 *tn = 1;
366 }
367 return un;
368 }
369 if (c < 0) {
370 LMMP_SWAP(up, vp, mp_srcptr);
371 sw = 1;
372 }
373 }
374 // U > V > 0(un >= vn),up/vp 为值序大/小者
375
376 mp_size_t n0 = un;
377 /* 一次分配:数对/修补对/矩阵/行/scratch/S/导出与尾组合暂存 */
378 mp_size_t mcap = 2 * n0 / 3 + 4; /* M1 每元素容量(p >= n/3 时片长 <= 2n/3) */
379 mp_size_t scsz = lmmp_hgcd_scratch_size_(2 * n0 / 3 + 2) + 4 * n0 + 64;
380 mp_size_t wsz = (n0 + 1) * 4 /* wa/wb/sa/sb */
381 + 4 * mcap /* M1 矩阵(尾段 gb 复用) */
382 + (n0 + 2) * 2 /* 行 u0/u1 */
383 + scsz /* hgcd scratch 池 */
384 + (n0 + 2) /* S 暂存 */
385 + (2 * n0 + 4) * 2 /* 导出 nb/yt */
386 + (2 * n0 + 8) * 2; /* 尾组合积 p1/p2 */
387 mp_ptr wbuf = ALLOC_TYPE(wsz, mp_limb_t);
388 mp_ptr wa = wbuf;
389 mp_ptr wb = wbuf + (n0 + 1);
390 mp_ptr sa = wbuf + 2 * (n0 + 1);
391 mp_ptr sb = wbuf + 3 * (n0 + 1);
392 mp_ptr mbuf1 = wbuf + 4 * (n0 + 1);
393 mp_ptr u0p = mbuf1 + 4 * mcap;
394 mp_ptr u1p = u0p + (n0 + 2);
395 mp_ptr scbuf = u1p + (n0 + 2);
396 mp_ptr sp = scbuf + scsz; /* S 暂存 */
397 mp_ptr nb = sp + (n0 + 2);
398 mp_ptr yt = nb + (2 * n0 + 4);
399 mp_ptr p1b = yt + (2 * n0 + 4); /* 尾组合积 sigma*u1 */
400 mp_ptr p2b = p1b + (2 * n0 + 8); /* 尾组合积 tau*u0 */
401 lmmp_hgcd_scratch_t sc = {scbuf, scsz, 0};
402
403 /* 初始归约:U 长于 V 时一次除法(商丢弃——q 乘零行元素无需计算) */
404 mp_size_t n;
405 int rowz = 0; /* 初始归约后行为 (1,0)(首轮捷径取 M1 第 0 行、det 反号) */
406 if (un > vn) {
407 lmmp_div_(NULL, wb, up, un, vp, vn); /* a = U mod V 直写 wb(<= vn limbs) */
408 mp_size_t rn = lmmp_gcd_norm_(wb, vn);
409 if (rn == 0) {
410 /* V | U:g = V,系数 (S,T) = (0,1),按 sw 映射 */
411 lmmp_copy(dstg, vp, vn);
412 if (!sw) {
413 dsts[0] = 0;
414 *sn = 0;
415 if (dstt != NULL) {
416 dstt[0] = 1;
417 *tn = 1;
418 }
419 } else {
420 dsts[0] = 1;
421 *sn = 1;
422 if (dstt != NULL) {
423 dstt[0] = 0;
424 *tn = 0;
425 }
426 }
427 lmmp_free(wbuf);
428 return vn;
429 }
430 lmmp_copy(wa, vp, vn);
431 lmmp_zero(wb + rn, vn - rn);
432 n = vn;
433 rowz = 1; /* 归约已发生:行 (1,0)、det=-1(E_div 行 1) */
434 } else {
435 lmmp_copy(wa, up, un);
436 lmmp_copy(wb, vp, vn);
437 n = un;
438 }
439
440 /*
441 行 (u0,u1):未经归约时初值 (0,1)(V = 0*U + 1*V);初始归约后为
442 (1,0)(V = 1*V + 0*r,E_div = /q 1;1 0/ 的行 1,det=-1)。首轮 hgcd
443 成功后直接取 M1 的对应行((0,1)*M1 = 行1、(1,0)*M1 = 行0),免一次行乘
444 */
445 mp_size_t u0n = 0, u1n = 0;
446 int det = 1;
447 if (rowz) {
448 u0p[0] = 1;
449 u0n = 1;
450 det = -1;
451 } else {
452 u1p[0] = 1;
453 u1n = 1;
454 }
455 int rowinit = 0; /* 行是否已经历首轮 M1 初始化 */
456 int first = 1;
457 int term_g0 = 0; /* (g;0) 终态(g 在 wa,长度 n) */
458 while (n > HGCD_RECURSE_THRESHOLD) {
459 /*
460 失衡守卫(与 lmmp_gcd_hgcd_ 的预归约同策略):b 归一化后不足公共长
461 的一半时,core 的高位片 (wa+p; wb+p) 中 b 部分全零,递归内部违反
462 a>b>0 前提——直接走除法步把 a 归约到 b 规模再平衡
463 */
464 mp_size_t nb_cur = lmmp_gcd_norm_(wb, n);
465 int degenerate = (2 * nb_cur <= n);
466 mp_size_t p = first ? n / 2 : n / 3;
467 mp_size_t nn = 0;
469 int dsub = 1;
470 if (!degenerate) {
471 first = 0;
472 lmmp_gcd_matrix_init_buf_(&M1, mbuf1, n - p + 2);
473 sc.used = 0;
474 nn = lmmp_hgcd_core_(&M1, wa + p, wb + p, n - p, &sc, &dsub, 0);
475 }
476 if (nn > 0) {
477 sc.used = 0;
478 mp_size_t blen = 0;
479 mp_size_t rn = lmmp_hgcd_adjust_(&M1, dsub, sa, sb, &blen, wa + p, wb + p, nn, wa, wb,
480 n, p, &sc);
481 sc.used = 0;
483 if (rn > 0 && rn < n && blen > maxlen) {
484 lmmp_copy(wa, sa, rn);
485 lmmp_copy(wb, sb, rn);
486 if (lmmp_cmp_(wa, wb, rn) < 0) {
487 LMMP_SWAP(wa, wb, mp_ptr); /* 指针交换后基址偏离 wbuf,仅长度域内使用 */
489 dsub = -dsub;
490 }
491 if (!rowinit) {
492 /* 行 <- M1 对应行((0,1)*M1 = 行1;归约后 (1,0)*M1 = 行0),
493 M1 缓冲下一轮被重初始化,须拷出 */
494 int rr = rowz ? 0 : 1;
495 lmmp_copy(u0p, M1.m[rr][0], M1.n[rr][0]);
496 u0n = M1.n[rr][0];
497 lmmp_copy(u1p, M1.m[rr][1], M1.n[rr][1]);
498 u1n = M1.n[rr][1];
499 det = rowz ? -dsub : dsub; /* E_div 的 det=-1 已并入 */
500 rowinit = 1;
501 } else {
502 gcdext_row_mul_(u0p, u1p, &u0n, &u1n, &M1, &sc);
503 det *= dsub;
504 }
505 n = rn;
506 continue;
507 }
508 }
509 /*
510 core 失败或修补被拒:除法步。core 失败多为近邻对(商 1)——先做
511 一次减法 r = a - b,行为纯加(原位 addmul+对调);r >= b 时商 >= 2,
512 做一次除法 a = q*b + r(商标量走原位 addmul,多 limb 走全乘)。
513 行 <- (q*u0 + u1, u0),detsign 变号;余数为 0 即终态 (g;0)
514 */
515 {
516 mp_size_t mark = sc.used;
517 /* 试减 r1 = a - b(a > b 无借位;r1 < b ⟺ 商为 1) */
518 lmmp_sub_(sa, wa, n, wb, nb_cur);
519 mp_size_t r1n = lmmp_gcd_norm_(sa, n);
520 if (r1n < nb_cur || (r1n == nb_cur && lmmp_cmp_(sa, wb, r1n) < 0)) {
521 /* 商为 1(含 r1 == 0 终态):数对 (b; r1) */
522 gcdext_row_qscalar_(&u0p, &u1p, &u0n, &u1n, 1);
523 det = -det;
524 rowinit = 1;
525 sc.used = mark;
526 if (r1n == 0) {
527 LMMP_SWAP(wa, wb, mp_ptr); /* g = wb(除数),移入 wa 统一终态 */
528 n = nb_cur;
529 term_g0 = 1;
530 break;
531 }
532 lmmp_copy(wa, wb, nb_cur);
533 lmmp_zero(wa + nb_cur, n - nb_cur);
534 lmmp_copy(wb, sa, r1n);
535 lmmp_zero(wb + r1n, nb_cur - r1n);
536 n = nb_cur;
537 continue;
538 }
539 /* 商 >= 2:全除法 a = q*b + r,余数直写 sa(eqsep 契约) */
540 mp_ptr q = lmmp_hgcd_salloc_(&sc, n + 2);
541 lmmp_div_(q, sa, wa, n, wb, nb_cur);
542 mp_size_t qn = n - nb_cur + 1 - (q[n - nb_cur] == 0);
543 mp_size_t rn = lmmp_gcd_norm_(sa, nb_cur);
544 if (qn == 1 && q[0] < (1ull << 63)) {
545 /* 商为标量:行原位 addmul + 对调 */
546 gcdext_row_qscalar_(&u0p, &u1p, &u0n, &u1n, q[0]);
547 } else if (u0n == 0) {
548 /* u0 为零:new_u0 = u1,new_u1 = 0(指针对调即可) */
549 LMMP_SWAP(u0p, u1p, mp_ptr);
550 LMMP_SWAP(u0n, u1n, mp_size_t);
551 } else {
552 /* 多 limb 商:new_u0 = q*u0 + u1(积 <= V/g <= n0+1 limb) */
553 mp_ptr t1 = lmmp_hgcd_salloc_(&sc, qn + u0n + 2);
554 lmmp_gcd_mul_(t1, q, qn, u0p, u0n);
555 mp_size_t pn = qn + u0n;
556 while (pn > 0 && t1[pn - 1] == 0)
557 --pn;
558 mp_ptr r0 = lmmp_hgcd_salloc_(&sc, n0 + 2);
559 mp_size_t r0n = 0;
560 if (u1n == 0) {
561 lmmp_copy(r0, t1, pn);
562 r0n = pn;
563 } else {
564 mp_limb_t c = (pn >= u1n) ? lmmp_add_(r0, t1, pn, u1p, u1n)
565 : lmmp_add_(r0, u1p, u1n, t1, pn);
566 r0n = pn > u1n ? pn : u1n;
567 if (c != 0)
568 r0[r0n++] = c;
569 }
570 lmmp_copy(u1p, u0p, u0n); /* new_u1 = 旧 u0 */
571 u1n = u0n;
572 lmmp_copy(u0p, r0, r0n);
573 u0n = r0n;
574 }
575 rowinit = 1;
576 det = -det;
577 sc.used = mark;
578 if (rn == 0) {
579 /* g = wb(除数),移入 wa 统一终态 */
580 LMMP_SWAP(wa, wb, mp_ptr);
581 n = nb_cur;
582 term_g0 = 1;
583 break;
584 }
585 /* 数对 (b; r):b 入 wa,r(sa)入 wb,公共长 nb_cur */
586 lmmp_copy(wa, wb, nb_cur);
587 lmmp_zero(wa + nb_cur, n - nb_cur);
588 lmmp_copy(wb, sa, rn);
589 lmmp_zero(wb + rn, nb_cur - rn);
590 n = nb_cur;
591 }
592 }
593
594 /* ---------------- 尾段与发射 ---------------- */
595 mp_size_t gn = 0;
596 mp_size_t sun = 0; /* S(值序大者系数)幅度长 */
597 int suneg = 0;
598 if (term_g0) {
599 gn = n;
600 sun = gcdext_pick_s_(sp, &suneg, u0p, u0n, u1p, u1n, det, sa);
601 lmmp_gcdext_emit_(dstg, dsts, sn, dstt, tn, wa, gn, sp, sun, suneg, sw, up, un, vp, vn, nb,
602 yt, p1b);
603 } else {
604 /* Lehmer 尾:当前对 (wa,wb) 取极小系数 (sigma,tau),
605 S = det*(sigma*u1 - tau*u0)(两次乘 + 符号-幅度组合) */
606 mp_size_t ra = lmmp_gcd_norm_(wa, n);
607 mp_size_t rb = lmmp_gcd_norm_(wb, n);
608 mp_ptr gb = mbuf1; /* <= n <= 64 limb(循环已降至阈值下),mcap 足够 */
609 mp_ptr sgp = sa;
610 mp_ptr taup = sb;
611 mp_ssize_t snp, tnp;
612 gn = lmmp_gcdext_lehmer_(gb, sgp, &snp, taup, &tnp, wa, ra, wb, rb);
613 mp_size_t snabs = snp < 0 ? -snp : snp;
614 mp_size_t tnabs = tnp < 0 ? -tnp : tnp;
615 mp_size_t p1n = 0, p2n = 0;
616 if (snabs != 0 && u1n != 0) {
617 lmmp_gcd_mul_(p1b, sgp, snabs, u1p, u1n);
618 p1n = snabs + u1n;
619 while (p1n > 0 && p1b[p1n - 1] == 0)
620 --p1n;
621 }
622 if (tnabs != 0 && u0n != 0) {
623 lmmp_gcd_mul_(p2b, taup, tnabs, u0p, u0n);
624 p2n = tnabs + u0n;
625 while (p2n > 0 && p2b[p2n - 1] == 0)
626 --p2n;
627 }
628 /* S = sigma*u1 + (-tau)*u0(第二项符号 = τ 取负),符号-幅度组合 */
629 lmmp_gcdext_smag_(sp, &sun, &suneg, p1b, p1n, snp < 0, p2b, p2n, !(tnp < 0));
630 if (det < 0 && sun != 0)
631 suneg = !suneg;
632 /*
633 极小化:S 落在正确的格类(det*(sigma*m11-tau*m10) ≡ S_true (mod V/g)),
634 但可能偏离极小代表元至多若干步(|K| <= V/(2g)*(1+o(1)),步数有界)。
635 快测 2*g*|S| <= V(⟺ |S| <= D/2,D = V/g):一次 sn*gn 乘 + 比较,
636 多数输入直接通过,免算 D 的整除;未过时按 D 向 0 平移至 |S| <= D/2;
637 平局(2|S| == D)恒取正(该侧配对系数满足 |t| <= U/(2g),另一侧
638 |g + D*U/2| > D*U/2 必越界)
639 */
640 if (sun != 0) {
641 lmmp_gcd_mul_(p1b, sp, sun, gb, gn); /* |S|*g */
642 mp_size_t pn = sun + gn;
643 while (pn > 0 && p1b[pn - 1] == 0)
644 --pn;
645 mp_limb_t c2 = lmmp_mul_1_(p2b, p1b, pn, 2); /* 2*|S|*g */
646 mp_size_t twon = pn + (c2 != 0);
647 int cmp2 = (twon != vn) ? (twon < vn ? -1 : 1) : lmmp_cmp_(p2b, vp, vn);
648 if (cmp2 > 0) {
649 mp_ptr db = p1b; /* D = V/g(恒等式保证整除,商长度 vn-gn+1) */
650 lmmp_div_(db, NULL, vp, vn, gb, gn);
651 mp_size_t dnn = vn - gn + 1;
652 while (dnn > 0 && db[dnn - 1] == 0)
653 --dnn;
654 for (;;) {
655 mp_limb_t c2s = lmmp_mul_1_(p2b, sp, sun, 2);
656 mp_size_t twosn = sun + (c2s != 0);
657 int cmp2s = (twosn != dnn) ? (twosn < dnn ? -1 : 1) : lmmp_cmp_(p2b, db, dnn);
658 if (cmp2s < 0)
659 break;
660 if (cmp2s == 0) {
661 suneg = 0; /* 平局恒取正 */
662 break;
663 }
664 int cD = (sun != dnn) ? (sun < dnn ? -1 : 1) : lmmp_cmp_(sp, db, dnn);
665 if (cD >= 0) {
666 lmmp_sub_(sp, sp, sun, db, dnn);
667 while (sun > 0 && sp[sun - 1] == 0)
668 --sun;
669 } else {
670 lmmp_sub_(sp, db, dnn, sp, sun);
671 sun = dnn;
672 while (sun > 0 && sp[sun - 1] == 0)
673 --sun;
674 suneg = !suneg;
675 }
676 if (sun == 0) {
677 suneg = 0;
678 break;
679 }
680 }
681 } else if (cmp2 == 0) {
682 suneg = 0; /* 平局恒取正 */
683 }
684 }
685 lmmp_gcdext_emit_(dstg, dsts, sn, dstt, tn, gb, gn, sp, sun, suneg, sw, up, un, vp, vn, nb,
686 yt, p1b);
687 }
688 lmmp_free(wbuf);
689 return gn;
690}
691
693 mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn) {
694 lmmp_param_assert(un > 0 && vn > 0);
695 lmmp_param_assert(up != NULL && vp != NULL && dstg != NULL && dsts != NULL && sn != NULL);
696 lmmp_param_assert(up[un - 1] != 0 && vp[vn - 1] != 0);
697
698 if (vn == 1)
699 return lmmp_gcdext_1_(dstg, dsts, sn, dstt, tn, up, un, vp[0]);
700 if (vn == 2 && un > 2)
701 return lmmp_gcdext_2_(dstg, dsts, sn, dstt, tn, up, un, vp);
702 if (vn >= GCD_HGCD_THRESHOLD && un >= GCD_HGCD_THRESHOLD)
703 return lmmp_gcdext_hgcd_(dstg, dsts, sn, dstt, tn, up, un, vp, vn);
704 return lmmp_gcdext_lehmer_(dstg, dsts, sn, dstt, tn, up, un, vp, vn);
705}
706
708 lmmp_param_assert(u > 0 && m > 0);
709
710 if (m == 1)
711 return 0; // 模 1:逆元存在且为 0
712 ulong r = u % m;
713 if (r == 0)
714 return 0; // m | u 且 m > 1:无逆
715 slong s;
716 ulong g = lmmp_gcdext_11_(r, m, &s, NULL);
717 if (g != 1)
718 return 0;
719 // s*r = 1 (mod m),|s| <= m/2 → 归一化到 [0,m)
720 ulong sm = s < 0 ? (ulong)-s : (ulong)s;
721 return s < 0 ? m - sm : sm;
722}
723
725 lmmp_param_assert(un > 0 && mn > 0);
726 lmmp_param_assert(up != NULL && mp != NULL && dst != NULL);
727 lmmp_param_assert(up[un - 1] != 0 && mp[mn - 1] != 0);
728
729 if (mn == 1) {
730 if (mp[0] == 1) {
731 dst[0] = 0;
732 return 1; // 模 1:逆元存在且为 0
733 }
734 ulong inv = lmmp_modinv_ulong_(lmmp_mod_1_(up, un, mp[0]), mp[0]);
735 if (inv == 0)
736 return 0;
737 dst[0] = inv;
738 return 1;
739 }
740
744 mp_ptr s = BALLOC_TYPE(mn + 1, mp_limb_t);
745 /* lmmp_div_ 要求 na>=nb:un<mn 时 u<m,余数即 u 自身 */
746 mp_size_t rn;
747 if (un < mn) {
748 lmmp_copy(r, up, un);
749 rn = un;
750 } else {
751 lmmp_div_(NULL, r, up, un, mp, mn);
752 rn = mn;
753 }
754 while (rn > 0 && r[rn - 1] == 0)
755 --rn;
756 if (rn == 0) {
758 return 0; // m | u 且 m > 1:无逆
759 }
760 mp_ssize_t sn;
761 mp_size_t gn = lmmp_gcdext_(g, s, &sn, NULL, NULL, r, rn, mp, mn);
762 if (gn != 1 || g[0] != 1) {
764 return 0;
765 }
766 /* s*r = 1 (mod m) → s*u = 1 (mod m)。s<0 时逆元 = m - |s|(|s| <= m/2
767 保证结果落在 (m/2, m),无借位);防御性上界复查后归一化 */
768 mp_size_t snn = sn < 0 ? -sn : sn;
769 lmmp_debug_assert(snn > 0 && snn <= mn);
770 if (sn < 0) {
771 lmmp_sub_(s, mp, mn, s, snn);
772 snn = mn;
773 }
774 if (snn == mn && lmmp_cmp_(s, mp, mn) >= 0) {
775 lmmp_sub_(s, s, mn, mp, mn);
776 }
777 while (snn > 0 && s[snn - 1] == 0)
778 --snn;
779 lmmp_debug_assert(snn > 0);
780 lmmp_copy(dst, s, snn);
782 return snn;
783}
#define xn
mp_size_t lmmp_hgcd_scratch_size_(mp_size_t n)
计算 hgcd 内部临时空间大小(容量上界推导见 hgcd.c 定义处注)
定义 hgcd.c:162
static void lmmp_gcdext_smag_(mp_ptr dst, mp_size_t *n, int *neg, mp_srcptr x, mp_size_t xn, int xneg, mp_srcptr y, mp_size_t yn, int yneg)
定义 gcd.h:169
mp_size_t lmmp_hgcd_core_(lmmp_hgcd_matrix_t *M, mp_ptr ap, mp_ptr bp, mp_size_t n, lmmp_hgcd_scratch_t *sc, int *detsign, int appr)
hgcd 递归核:将数对归约至约 n/2 规模并累积变换矩阵(详见 hgcd.c 实现注)
static mp_size_t lmmp_gcd_norm_(mp_srcptr p, mp_size_t n)
定义 gcd.h:49
mp_size_t lmmp_hgcd_adjust_(lmmp_hgcd_matrix_t *M1, int detsign, mp_ptr dap, mp_ptr dbp, mp_size_t *blen, mp_srcptr ha, mp_srcptr hb, mp_size_t hn0, mp_srcptr ap, mp_srcptr bp, mp_size_t n, mp_size_t p, lmmp_hgcd_scratch_t *sc)
高位直写 + 低位修补:将子递归成果(矩阵 M1 与归约后的高位对)合入完整数对
定义 hgcd.c:554
mp_size_t lmmp_gcdext_derive_(mp_ptr dst, int *tneg, mp_srcptr gp, mp_size_t gn, mp_srcptr sp, mp_size_t sn, int sneg, mp_srcptr xp, mp_size_t xn, mp_srcptr yp, mp_size_t yn, mp_ptr nb, mp_ptr yt, mp_ptr qt)
导出另一侧系数:tv = (g - S·X)/Y(S 为 X 侧系数,恒等式保证整除)
#define HGCD_RECURSE_THRESHOLD
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 gcd.h:33
static mp_ptr lmmp_hgcd_salloc_(lmmp_hgcd_scratch_t *sc, mp_size_t n)
定义 gcd.h:42
static mp_size_t lmmp_gcd_matrix_maxlen_(const lmmp_hgcd_matrix_t *M)
定义 gcd.h:56
static void lmmp_gcd_mul_(mp_ptr dst, mp_srcptr a, mp_size_t an, mp_srcptr b, mp_size_t bn)
定义 gcd.h:92
void lmmp_gcdext_emit_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr gp, mp_size_t gn, mp_srcptr sp, mp_size_t sun, int suneg, int sw, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn, mp_ptr nb, mp_ptr yt, mp_ptr qt)
发射:g 与 S(值序大者系数)按 sw 映射到 (dsts,dstt),另一系数经恒等式导出
static void lmmp_gcd_matrix_init_buf_(lmmp_hgcd_matrix_t *M, mp_ptr buf, mp_size_t alloc)
定义 gcd.h:77
static void lmmp_gcd_matrix_swap_cols_(lmmp_hgcd_matrix_t *M)
定义 gcd.h:70
static mp_size_t gcdext_pick_s_(mp_ptr sp, int *sneg, mp_srcptr u0p, mp_size_t u0n, mp_srcptr u1p, mp_size_t u1n, int det, mp_ptr t1)
static void gcdext_row_qscalar_(mp_ptr *u0p, mp_ptr *u1p, mp_size_t *u0n, mp_size_t *u1n, ulong q)
Copyright (C) 2026 HJimmyK (Jericho Knox)
static void gcdext_row_mul_(mp_ptr u0p, mp_ptr u1p, mp_size_t *u0n, mp_size_t *u1n, const lmmp_hgcd_matrix_t *M1, lmmp_hgcd_scratch_t *sc)
mp_limb_t * mp_ptr
定义 lmmp.h:96
#define LMMP_SWAP(x, y, type)
交换两个变量的值
定义 lmmp.h:458
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474
#define lmmp_zero(dst, n)
定义 lmmp.h:476
uint64_t mp_size_t
定义 lmmp.h:93
#define lmmp_debug_assert(x)
定义 lmmp.h:498
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
int64_t mp_ssize_t
定义 lmmp.h:95
uint64_t mp_limb_t
定义 lmmp.h:92
#define LMMP_VECT_CONSERVATIVE
定义 lmmp.h:201
#define lmmp_param_assert(x)
定义 lmmp.h:509
static mp_limb_t lmmp_add_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
加法静态内联函数 [dst,na]=[numa,na]+[numb,nb]
static mp_limb_t lmmp_add_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
加单精度数静态内联函数 [dst,na]=[numa,na]+x
mp_limb_t lmmp_shr_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_size_t shr)
右移操作 [dst,na] = [numa,na]>>shr,dst的高shr位填充0
定义 shr.c:26
mp_limb_t lmmp_mod_1_(mp_srcptr numa, mp_size_t na, mp_limb_t x)
单精度数取余
定义 div.c:38
void lmmp_mul_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
不等长乘法操作 [dst,na+nb] = [numa,na] * [numb,nb]
int lmmp_cmp_(mp_srcptr numa, mp_srcptr numb, mp_size_t n)
比较函数
定义 cmp.c:26
static mp_limb_t lmmp_sub_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
减法静态内联函数 [dst,na]=[numa,na]-[numb,nb]
mp_limb_t lmmp_addmul_1_(mp_ptr numa, mp_srcptr numb, mp_size_t n, mp_limb_t b)
乘以单limb并累加操作 [numa,n] += [numb,n] * b
定义 mul_1.c:76
mp_limb_t lmmp_mul_1_(mp_ptr dst, mp_srcptr numa, mp_size_t na, mp_limb_t x)
乘以单limb操作 [dst,na] = [numa,na] * x
定义 mul_1.c:27
void lmmp_div_(mp_ptr dstq, mp_ptr dstr, mp_srcptr numa, mp_size_t na, mp_srcptr numb, mp_size_t nb)
除法和取模操作
定义 div.c:85
#define ctz_shr_u64(r, x, cnt)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define xp
#define r0
#define s
#define n
#define GCD_HGCD_THRESHOLD
ulong lmmp_gcdext_11_(ulong u, ulong v, slong *s, slong *t)
扩展欧几里得(双 limb 标量):g = gcd(u,v),s*u + t*v = g
void lmmp_divexact_(mp_ptr dst, mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
精确除法([dst,nn]=[np,nn]/[dp,dn],且余数必须为0)
ulong lmmp_modinv_ulong_(ulong u, ulong m)
模逆元(单 limb):求 u^{-1} mod m
mp_size_t lmmp_modinv_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr mp, mp_size_t mn)
模逆元(任意长度):求 [up,un]^{-1} mod [mp,mn]
int64_t slong
定义 numth.h:41
mp_size_t lmmp_gcdext_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
扩展欧几里得(通用分发入口):g = gcd(u,v),s*u + t*v = g
mp_size_t lmmp_gcdext_2_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, mp_srcptr vp)
扩展欧几里得(任意长度对双 limb):g = gcd([up,un],[vp,2]),s*u + t*v = g
uint64_t ulong
定义 numth.h:39
mp_size_t lmmp_gcdext_1_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, ulong v)
扩展欧几里得(任意长度对单 limb):g = gcd([up,un],v),s*u + t*v = g
mp_size_t lmmp_gcdext_hgcd_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
扩展欧几里得(hgcd 分治,长输入优选):g = gcd(u,v),s*u + t*v = g
mp_size_t lmmp_gcdext_lehmer_(mp_ptr dstg, mp_ptr dsts, mp_ssize_t *sn, mp_ptr dstt, mp_ssize_t *tn, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
扩展欧几里得(Lehmer 算法):g = gcd(u,v),s*u + t*v = g
hgcd 变换矩阵
#define M1
#define ALLOC_TYPE(n, type)
#define TEMP_B_DECL
#define BALLOC_TYPE(n, type)
#define TEMP_B_FREE