nx_classical_unpatented_3.nx source
↩ module page · 178 lines · 5219 B
1// nx_classical_unpatented_3.nx -- batch 3 of unpatented algorithms:
2// 4 hash functions + 4 array transformations. All public domain.
3
4// nx_safety_envelope:
5// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
6// sil_target: SIL1
7// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
8// verdict: NOT_YET_EVALUATED
9
10import "nx_syscalls.nx"
11import "nx_tier.nx"
12const K_MAGIC_2166136261: i64 = 2166136261
13const K_MAGIC_16777619: i64 = 16777619
14const K_MAGIC_5381: i64 = 5381
15const K_MAGIC_65521: i64 = 65521
16
17// ===== 19. FNV-1a 32-bit (Fowler/Noll/Vo 1991, public domain) =======
18//
19// 32-bit FNV-1a hash over n bytes. Authors explicitly released to
20// public domain. Faster + better-distributed than FNV-0; widely used
21// in routers, hash tables, bloom filters.
22//
23// FNV32_OFFSET = 2166136261 (0x811C9DC5)
24// FNV32_PRIME = 16777619 (0x01000193)
25//
26// Mask the running hash to 32 bits each step to stay in u32 semantics.
27func nx_fnv1a_32_buf(buf: *u8, n: nx_size) -> nx_int {
28 var h: nx_int = K_MAGIC_2166136261
29 var i: nx_size = 0
30 while i < n {
31 h = h ^ (buf[i] as nx_int)
32 h = (h * K_MAGIC_16777619) & 0xFFFFFFFF
33 i = i + 1
34 }
35 return h
36}
37
38// ===== 20. djb2 (Dan Bernstein 1991, public domain) =================
39//
40// hash = 5381; for each byte: hash = hash*33 + byte. Very fast, used
41// in shell utilities, glibc internals, etc. Public domain.
42func nx_djb2_buf(buf: *u8, n: nx_size) -> nx_int {
43 var h: nx_int = K_MAGIC_5381
44 var i: nx_size = 0
45 while i < n {
46 h = ((h * 33) + (buf[i] as nx_int)) & 0xFFFFFFFFFFFFFFFF
47 i = i + 1
48 }
49 return h
50}
51
52// ===== 21. Jenkins one-at-a-time (Bob Jenkins, public domain) =======
53//
54// 32-bit hash; popular in Perl, Linux dcache. Author Bob Jenkins
55// explicitly placed in public domain at burtleburtle.net.
56func nx_jenkins_oaat_buf(buf: *u8, n: nx_size) -> nx_int {
57 var h: nx_int = 0
58 var i: nx_size = 0
59 while i < n {
60 h = h + (buf[i] as nx_int)
61 h = (h + (h << 10)) & 0xFFFFFFFF
62 h = h ^ (h >> 6)
63 i = i + 1
64 }
65 h = (h + (h << 3)) & 0xFFFFFFFF
66 h = h ^ (h >> 11)
67 h = (h + (h << 15)) & 0xFFFFFFFF
68 return h
69}
70
71// ===== 22. Adler-32 (Mark Adler 1995, public domain via RFC 1950) ===
72//
73// 32-bit checksum used by zlib. Two running sums mod 65521 (largest
74// prime less than 2^16). Public domain per RFC 1950.
75func nx_adler32_buf(buf: *u8, n: nx_size) -> nx_int {
76 var a: nx_int = 1
77 var b: nx_int = 0
78 var i: nx_size = 0
79 while i < n {
80 a = (a + (buf[i] as nx_int)) - ((a + (buf[i] as nx_int)) / K_MAGIC_65521) * K_MAGIC_65521
81 b = (b + a) - ((b + a) / K_MAGIC_65521) * K_MAGIC_65521
82 i = i + 1
83 }
84 return (b << 16) | a
85}
86
87// ===== 23. In-place array reversal (folklore) =======================
88func nx_array_reverse_inplace(arr: *nx_int, n: nx_idx) -> nx_int {
89 if n < 2 { return 0 }
90 var i: nx_idx = 0
91 var j: nx_idx = n - 1
92 while i < j {
93 let t: nx_int = arr[i]
94 arr[i] = arr[j]
95 arr[j] = t
96 i = i + 1
97 j = j - 1
98 }
99 return 0
100}
101
102// ===== 24. Left rotation by k positions (classical) =================
103//
104// Rotates arr[0..n) left by k positions using the three-reversal trick:
105// reverse(0, k), reverse(k, n), reverse(0, n). O(n) time, O(1) memory.
106// Public domain; standard CS textbook material.
107func nx_array_rotate_left(arr: *nx_int, n: nx_idx, k: nx_idx) -> nx_int {
108 if n < 2 { return 0 }
109 let m: nx_idx = k - (k / n) * n // k mod n
110 if m == 0 { return 0 }
111 // reverse [0, m)
112 var i: nx_idx = 0
113 var j: nx_idx = m - 1
114 while i < j {
115 let t: nx_int = arr[i]
116 arr[i] = arr[j]
117 arr[j] = t
118 i = i + 1
119 j = j - 1
120 }
121 // reverse [m, n)
122 i = m
123 j = n - 1
124 while i < j {
125 let t: nx_int = arr[i]
126 arr[i] = arr[j]
127 arr[j] = t
128 i = i + 1
129 j = j - 1
130 }
131 // reverse [0, n)
132 i = 0
133 j = n - 1
134 while i < j {
135 let t: nx_int = arr[i]
136 arr[i] = arr[j]
137 arr[j] = t
138 i = i + 1
139 j = j - 1
140 }
141 return 0
142}
143
144// ===== 25. Lomuto partition (Quicksort foundation, Hoare 1961) ======
145//
146// Partitions arr[0..n) around the LAST element as pivot. After return,
147// arr[0..returned) <= pivot < arr[returned..n). Returns the pivot's
148// final index. Public domain.
149func nx_partition_lomuto(arr: *nx_int, n: nx_idx) -> nx_idx {
150 if n == 0 { return 0 }
151 let pivot: nx_int = arr[n - 1]
152 var store: nx_idx = 0
153 var i: nx_idx = 0
154 while i < n - 1 {
155 if arr[i] <= pivot {
156 let t: nx_int = arr[i]
157 arr[i] = arr[store]
158 arr[store] = t
159 store = store + 1
160 }
161 i = i + 1
162 }
163 let t2: nx_int = arr[store]
164 arr[store] = arr[n - 1]
165 arr[n - 1] = t2
166 return store
167}
168
169// ===== 26. Count occurrences (folklore) =============================
170func nx_count_occurrences(arr: *nx_int, n: nx_idx, target: nx_int) -> nx_int {
171 var c: nx_int = 0
172 var i: nx_idx = 0
173 while i < n {
174 if arr[i] == target { c = c + 1 }
175 i = i + 1
176 }
177 return c
178}