Hugging Face's logo

AryaWu
/
coreutils

Model card Files
xet
Community
coreutils
File size: 4,940 Bytes 
78d2150
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
 
#include "../../unity/unity.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

/* Unity requires these even if empty */
void setUp(void) {
  /* Setup code here, or leave empty */
}
void tearDown(void) {
  /* Cleanup code here, or leave empty */
}

/* Helper: find the index of a given small prime in primes_ptab.
   Returns -1 if not found (should not happen for small primes we use). */
static int find_prime_index(mp_limb_t prime)
{
  for (int i = 0; i < PRIMES_PTAB_ENTRIES; i++)
    {
      if ((mp_limb_t)primes_ptab[i] == prime)
        return i;
    }
  return -1;
}

/* Helper: compute the base index and offset (ioff) for a given index,
   matching the 8-way unrolling the kernel supports. */
static void base_and_offset_for_index(int idx, int *base, int *ioff)
{
  int off = idx % 8;
  *ioff = off;
  *base = idx - off;
}

static void init_factors(struct factors *f)
{
  memset(f, 0, sizeof(*f));
}

void test_divblock_divides_once_by_3(void)
{
  int idx = find_prime_index(3);
  TEST_ASSERT_NOT_EQUAL(-1, idx);
  int base = 0, off = 0;
  base_and_offset_for_index(idx, &base, &off);
  TEST_ASSERT_EQUAL_INT(idx, base + off);

  struct factors f; init_factors(&f);
  mp_limb_t t0 = (mp_limb_t)3;
  mp_limb_t r = divblock(&f, t0, &primes_dtab[base], (idx_t)base, off);

  TEST_ASSERT(r == (mp_limb_t)1);
  TEST_ASSERT(f.nfactors == 1);
  TEST_ASSERT(f.p[0] == (mp_limb_t)3);
  TEST_ASSERT(f.e[0] == 1);
}

void test_divblock_divides_twice_by_3(void)
{
  int idx = find_prime_index(3);
  TEST_ASSERT_NOT_EQUAL(-1, idx);
  int base = 0, off = 0;
  base_and_offset_for_index(idx, &base, &off);

  struct factors f; init_factors(&f);
  mp_limb_t t0 = (mp_limb_t)9; /* 3^2 */
  mp_limb_t r = divblock(&f, t0, &primes_dtab[base], (idx_t)base, off);

  TEST_ASSERT(r == (mp_limb_t)1);
  TEST_ASSERT(f.nfactors == 1);
  TEST_ASSERT(f.p[0] == (mp_limb_t)3);
  TEST_ASSERT(f.e[0] == 2);
}

void test_divblock_non_divisible_returns_input(void)
{
  int idx = find_prime_index(3);
  TEST_ASSERT_NOT_EQUAL(-1, idx);
  int base = 0, off = 0;
  base_and_offset_for_index(idx, &base, &off);

  struct factors f; init_factors(&f);
  mp_limb_t t0 = (mp_limb_t)10; /* Not divisible by 3 */
  mp_limb_t r = divblock(&f, t0, &primes_dtab[base], (idx_t)base, off);

  TEST_ASSERT(r == t0);
  TEST_ASSERT(f.nfactors == 0);
}

void test_divblock_returns_remaining_quotient_after_divisions(void)
{
  int idx = find_prime_index(3);
  TEST_ASSERT_NOT_EQUAL(-1, idx);
  int base = 0, off = 0;
  base_and_offset_for_index(idx, &base, &off);

  struct factors f; init_factors(&f);
  /* t0 = 3^3 * 10 = 270, should divide out 3 three times and return 10 */
  mp_limb_t t0 = (mp_limb_t)27 * (mp_limb_t)10;
  mp_limb_t r = divblock(&f, t0, &primes_dtab[base], (idx_t)base, off);

  TEST_ASSERT(r == (mp_limb_t)10);
  TEST_ASSERT(f.nfactors == 1);
  TEST_ASSERT(f.p[0] == (mp_limb_t)3);
  TEST_ASSERT(f.e[0] == 3);
}

void test_divblock_works_with_nonzero_offset_prime_23(void)
{
  int idx = find_prime_index(23);
  TEST_ASSERT_NOT_EQUAL(-1, idx);
  int base = 0, off = 0;
  base_and_offset_for_index(idx, &base, &off);
  TEST_ASSERT(off >= 0 && off <= 7);
  TEST_ASSERT_EQUAL_INT(idx, base + off);

  struct factors f; init_factors(&f);
  mp_limb_t t0 = (mp_limb_t)23 * (mp_limb_t)7; /* 161 */
  mp_limb_t r = divblock(&f, t0, &primes_dtab[base], (idx_t)base, off);

  TEST_ASSERT(r == (mp_limb_t)7);
  TEST_ASSERT(f.nfactors == 1);
  TEST_ASSERT(f.p[0] == (mp_limb_t)23);
  TEST_ASSERT(f.e[0] == 1);
}

void test_divblock_increments_existing_factor_multiplicity(void)
{
  int idx = find_prime_index(5);
  TEST_ASSERT_NOT_EQUAL(-1, idx);
  int base = 0, off = 0;
  base_and_offset_for_index(idx, &base, &off);

  struct factors f; init_factors(&f);
  /* Pre-populate factors with prime 5 multiplicity 2 */
  f.nfactors = 1;
  f.p[0] = (mp_limb_t)5;
  f.e[0] = 2;

  mp_limb_t t0 = (mp_limb_t)5;
  mp_limb_t r = divblock(&f, t0, &primes_dtab[base], (idx_t)base, off);

  TEST_ASSERT(r == (mp_limb_t)1);
  TEST_ASSERT(f.nfactors == 1);
  TEST_ASSERT(f.p[0] == (mp_limb_t)5);
  TEST_ASSERT(f.e[0] == 3);
}

void test_divblock_t0_equal_1_no_change(void)
{
  int idx = find_prime_index(7);
  TEST_ASSERT_NOT_EQUAL(-1, idx);
  int base = 0, off = 0;
  base_and_offset_for_index(idx, &base, &off);

  struct factors f; init_factors(&f);
  mp_limb_t t0 = (mp_limb_t)1;
  mp_limb_t r = divblock(&f, t0, &primes_dtab[base], (idx_t)base, off);

  TEST_ASSERT(r == (mp_limb_t)1);
  TEST_ASSERT(f.nfactors == 0);
}

int main(void)
{
  UNITY_BEGIN();
  RUN_TEST(test_divblock_divides_once_by_3);
  RUN_TEST(test_divblock_divides_twice_by_3);
  RUN_TEST(test_divblock_non_divisible_returns_input);
  RUN_TEST(test_divblock_returns_remaining_quotient_after_divisions);
  RUN_TEST(test_divblock_works_with_nonzero_offset_prime_23);
  RUN_TEST(test_divblock_increments_existing_factor_multiplicity);
  RUN_TEST(test_divblock_t0_equal_1_no_change);
  return UNITY_END();
}