LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
ele_mul.c 文件参考
#include "numth/ele_mul.h"
#include "mparam.h"
ele_mul.c 的引用(Include)关系图:

浏览该文件的源代码.

宏定义

#define INSERTION_SORT_THRESHOLD   16
 Copyright (C) 2026 HJimmyK (Jericho Knox)

函数

static void insertion_sort (huff_node arr[], sint low, sint high)
 在闭区间 [low, high] 上进行插入排序
mp_size_t lmmp_elem_mul_ulong_ (mp_ptr restrict dst, const ulongp restrict limbs, mp_size_t n, mp_ptr restrict tp)
sint lmmp_huff_tree_build_ (huff_tree *restrict ht)
mp_size_t lmmp_huff_tree_mul_ (huff_tree *restrict ht, sint ridx, mp_ptr restrict dst, mp_ptr restrict tp)
static sint median_of_three (const huff_node arr[], sint a, sint b, sint c)
 返回 arr[a]、arr[b]、arr[c] 三个索引中对应值的中位数的索引
static void quicksort_rec (huff_node arr[], sint low, sint high)
 递归的三路快速排序,对闭区间 [low, high] 排序
static void swap_huff_node (huff_node *a, huff_node *b)

宏定义说明

◆ INSERTION_SORT_THRESHOLD

#define INSERTION_SORT_THRESHOLD   16

Copyright (C) 2026 HJimmyK (Jericho Knox)

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 ele_mul.c 第 26 行定义.

被这些函数引用 quicksort_rec().

函数说明

◆ insertion_sort()

void insertion_sort ( huff_node arr[],
sint low,
sint high )
static

在闭区间 [low, high] 上进行插入排序

在文件 ele_mul.c 第 40 行定义.

40 {
41 for (sint i = low + 1; i <= high; ++i) {
42 mp_srcptr np = arr[i].np;
43 mp_size_t nn = arr[i].nn;
44 sint j = i - 1;
45 while (j >= low && arr[j].nn > nn) {
46 arr[j + 1].np = arr[j].np;
47 arr[j + 1].nn = arr[j].nn;
48 --j;
49 }
50 arr[j + 1].np = np;
51 arr[j + 1].nn = nn;
52 }
53}
mp_size_t nn
mp_srcptr np
uint64_t mp_size_t
定义 lmmp.h:93
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
int32_t sint
定义 numth.h:40

引用了 insertion_sort(), huff_node::nn , 以及 huff_node::np.

被这些函数引用 insertion_sort() , 以及 quicksort_rec().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_elem_mul_ulong_()

mp_size_t lmmp_elem_mul_ulong_ ( mp_ptr restrict dst,
const ulongp restrict limbs,
mp_size_t n,
mp_ptr restrict tp )

在文件 ele_mul.c 第 172 行定义.

172 {
174 lmmp_param_assert(n > 0);
175 dst[0] = limbs[0];
176 mp_size_t rn = 1;
177 for (mp_size_t i = 1; i < n; i++) {
178 dst[rn] = lmmp_mul_1_(dst, dst, rn, limbs[i]);
179 rn++;
180 rn -= dst[rn - 1] == 0 ? 1 : 0;
181 }
182 return rn;
183 }
184 mp_size_t halfn = n / 2;
185 mp_size_t n1 = lmmp_elem_mul_ulong_(tp, limbs, halfn, dst);
186 mp_size_t n2 = lmmp_elem_mul_ulong_(tp + halfn, limbs + halfn, n - halfn, dst + halfn);
187 if (n1 > n2)
188 lmmp_mul_(dst, tp, n1, tp + halfn, n2);
189 else
190 lmmp_mul_(dst, tp + halfn, n2, tp, n1);
191 n = n1 + n2;
192 n -= dst[n - 1] == 0 ? 1 : 0;
193 return n;
194}
mp_size_t lmmp_elem_mul_ulong_(mp_ptr restrict dst, const ulongp restrict limbs, mp_size_t n, mp_ptr restrict tp)
#define lmmp_param_assert(x)
定义 lmmp.h:509
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]
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
#define tp
#define n
#define ELEM_MUL_BASECASE_THRESHOLD

引用了 ELEM_MUL_BASECASE_THRESHOLD, lmmp_elem_mul_ulong_(), lmmp_mul_(), lmmp_mul_1_(), lmmp_param_assert, n, restrict , 以及 tp.

被这些函数引用 lmmp_arith_seqprod_(), lmmp_elem_mul_ulong_(), lmmp_elem_mul_ulong_(), lmmp_factors_mul_(), lmmp_factors_mul_ushort_(), lmmp_odd_nPr_product_(), lmmp_odd_nPr_product_(), lmmp_odd_nPr_ulong_(), lmmp_odd_nPr_ushort_() , 以及 lmmp_primefac_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_huff_tree_build_()

sint lmmp_huff_tree_build_ ( huff_tree *restrict ht)

在文件 ele_mul.c 第 114 行定义.

114 {
115 lmmp_param_assert(ht != NULL);
116 lmmp_param_assert(ht->root != NULL && ht->size > 0);
117 sint n = ht->size;
118 huff_node* arr = ht->root;
119
120 if (n == 1) {
121 return 0;
122 }
123
124 quicksort_rec(arr, 0, n - 1);
125
126 sint i = 0, j = n, k = n;
127
128 while (k < (2 * n - 1)) {
129 sint idx1, idx2;
130
131 if (i < n && (j >= k || arr[i].nn <= arr[j].nn)) {
132 idx1 = i++;
133 } else {
134 idx1 = j++;
135 }
136
137 if (i < n && (j >= k || arr[i].nn <= arr[j].nn)) {
138 idx2 = i++;
139 } else {
140 idx2 = j++;
141 }
142 // 非叶子节点的np不会被访问,此赋值不会影响结果
143 //arr[k].np = NULL;
144 arr[k].nn = arr[idx1].nn + arr[idx2].nn;
145 arr[k].left = idx1;
146 arr[k].right = idx2;
147 k++;
148 }
149
150 return 2 * n - 2;
151}
#define k
static void quicksort_rec(huff_node arr[], sint low, sint high)
递归的三路快速排序,对闭区间 [low, high] 排序
huff_node * root
Copyright (C) 2026 HJimmyK (Jericho Knox)

引用了 k, huff_node::left, lmmp_huff_tree_build_(), lmmp_param_assert, n, huff_node::nn, quicksort_rec(), restrict , 以及 huff_node::right.

被这些函数引用 lmmp_huff_tree_build_() , 以及 lmmp_huff_tree_build_().

函数调用图:
这是这个函数的调用关系图:

◆ lmmp_huff_tree_mul_()

mp_size_t lmmp_huff_tree_mul_ ( huff_tree *restrict ht,
sint ridx,
mp_ptr restrict dst,
mp_ptr restrict tp )

在文件 ele_mul.c 第 153 行定义.

153 {
154 if (ht->root[ridx].left == -1) {
155 lmmp_copy(dst, ht->root[ridx].np, ht->root[ridx].nn);
156 return ht->root[ridx].nn;
157 } else {
158 sint idx = ht->root[ridx].left;
159 mp_size_t halfn = ht->root[idx].nn; // 左子树的limb缓冲区长度
160 mp_size_t n1 = lmmp_huff_tree_mul_(ht, ht->root[ridx].left, tp, dst);
161 mp_size_t n2 = lmmp_huff_tree_mul_(ht, ht->root[ridx].right, tp + halfn, dst + halfn);
162 if (n1 > n2)
163 lmmp_mul_(dst, tp, n1, tp + halfn, n2);
164 else
165 lmmp_mul_(dst, tp + halfn, n2, tp, n1);
166 n1 += n2;
167 n1 -= dst[n1 - 1] == 0 ? 1 : 0;
168 return n1;
169 }
170}
mp_size_t lmmp_huff_tree_mul_(huff_tree *restrict ht, sint ridx, mp_ptr restrict dst, mp_ptr restrict tp)
#define lmmp_copy(dst, src, n)
定义 lmmp.h:474

引用了 lmmp_copy, lmmp_huff_tree_mul_(), lmmp_mul_(), restrict , 以及 tp.

被这些函数引用 lmmp_huff_tree_mul_() , 以及 lmmp_huff_tree_mul_().

函数调用图:
这是这个函数的调用关系图:

◆ median_of_three()

sint median_of_three ( const huff_node arr[],
sint a,
sint b,
sint c )
inlinestatic

返回 arr[a]、arr[b]、arr[c] 三个索引中对应值的中位数的索引

在文件 ele_mul.c 第 58 行定义.

58 {
59 mp_size_t va = arr[a].nn, vb = arr[b].nn, vc = arr[c].nn;
60 if (va < vb) {
61 if (vb < vc)
62 return b;
63 else if (va < vc)
64 return c;
65 else
66 return a;
67 } else {
68 if (va < vc)
69 return a;
70 else if (vb < vc)
71 return c;
72 else
73 return b;
74 }
75}

引用了 median_of_three() , 以及 huff_node::nn.

被这些函数引用 median_of_three() , 以及 quicksort_rec().

函数调用图:
这是这个函数的调用关系图:

◆ quicksort_rec()

void quicksort_rec ( huff_node arr[],
sint low,
sint high )
static

递归的三路快速排序,对闭区间 [low, high] 排序

在文件 ele_mul.c 第 80 行定义.

80 {
81 if (high - low + 1 <= INSERTION_SORT_THRESHOLD) {
82 insertion_sort(arr, low, high);
83 return;
84 }
85
86 sint mid = low + (high - low) / 2;
87 sint pivot_index = median_of_three(arr, low, mid, high);
88 if (pivot_index != low) {
89 swap_huff_node(&arr[low], &arr[pivot_index]);
90 }
91 mp_size_t pivot = arr[low].nn;
92
93 sint lt = low; // 小于区域的右边界(开)
94 sint gt = high; // 大于区域的左边界(开)
95 sint i = low + 1;
96
97 while (i <= gt) {
98 if (arr[i].nn < pivot) {
99 swap_huff_node(&arr[lt], &arr[i]);
100 ++lt;
101 ++i;
102 } else if (arr[i].nn > pivot) {
103 swap_huff_node(&arr[i], &arr[gt]);
104 --gt;
105 } else {
106 ++i;
107 }
108 }
109
110 quicksort_rec(arr, low, lt - 1);
111 quicksort_rec(arr, gt + 1, high);
112}
#define INSERTION_SORT_THRESHOLD
Copyright (C) 2026 HJimmyK (Jericho Knox)
static void insertion_sort(huff_node arr[], sint low, sint high)
在闭区间 [low, high] 上进行插入排序
static sint median_of_three(const huff_node arr[], sint a, sint b, sint c)
返回 arr[a]、arr[b]、arr[c] 三个索引中对应值的中位数的索引
static void swap_huff_node(huff_node *a, huff_node *b)

引用了 insertion_sort(), INSERTION_SORT_THRESHOLD, median_of_three(), huff_node::nn, quicksort_rec() , 以及 swap_huff_node().

被这些函数引用 lmmp_huff_tree_build_() , 以及 quicksort_rec().

函数调用图:
这是这个函数的调用关系图:

◆ swap_huff_node()

void swap_huff_node ( huff_node * a,
huff_node * b )
inlinestatic

在文件 ele_mul.c 第 28 行定义.

28 {
29 mp_srcptr tp = a->np;
30 mp_size_t tn = a->nn;
31 a->np = b->np;
32 a->nn = b->nn;
33 b->np = tp;
34 b->nn = tn;
35}

引用了 huff_node::nn, huff_node::np, swap_huff_node() , 以及 tp.

被这些函数引用 quicksort_rec() , 以及 swap_huff_node().

函数调用图:
这是这个函数的调用关系图: