--Module:PythonScript/Librarys/StdAlgorithms
-- 1. base64
-- 2. fractions
-- 3. graphlib
-- 4. hash
-- 塞不下了。
local StdAlgorithms = {}
-- ==========================================
-- 1. base64 演算法
-- ==========================================
function StdAlgorithms.base64()
local b64_helper = {}
-- ==========================================
-- 1. 字元集定義與反向索引快取
-- ==========================================
b64_helper.chars = {
b64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/",
b64url = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_",
b32 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567",
b32hex = "0123456789ABCDEFGHIJKLMNOPQRSTUV",
b16 = "0123456789ABCDEF",
a85 = "!\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstu",
b85 = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz!#$%&()*+-;<=>?@^_`{|}~",
z85 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ.-:+=^!/*?&<>()[]{}@%$#"
}
b64_helper.inv_maps = {}
-- 延遲建立字元集的 O(1) 反向查找表 (byte -> 0-based index)
function b64_helper.get_inv_map(key, alphabet)
local map = b64_helper.inv_maps[key]
if not map then
map = {}
local alpha = alphabet or b64_helper.chars[key]
for i = 1, #alpha do
map[string.byte(alpha, i)] = i - 1
end
b64_helper.inv_maps[key] = map
end
return map
end
-- ==========================================
-- 2. 共通檢查、型別轉換與例外拋出輔助函式
-- ==========================================
function b64_helper.is_none(v)
return v == nil or (type(v) == "table" and v.__class and v.__class.__name == "NoneType")
end
function b64_helper.ensure_exceptions()
if not b64_helper.ErrorClass then
local PyClass = require("Module:沙盒/a2569875/PythonScript/Class")
local Runtime = require("Module:沙盒/a2569875/PythonScript/Runtime")
b64_helper.ErrorClass = PyClass.make_class("Error", { Runtime.builtins.ValueError }, {})
b64_helper.ErrorClass.__dict["__module__"] = "binascii"
b64_helper.IncompleteClass = PyClass.make_class("Incomplete", { Runtime.builtins.Exception }, {})
b64_helper.IncompleteClass.__dict["__module__"] = "binascii"
end
end
function b64_helper.raise_error(msg)
b64_helper.ensure_exceptions()
require("Module:沙盒/a2569875/PythonScript/Runtime").raise(b64_helper.ErrorClass, msg)
end
function b64_helper.make_bytes(raw_str)
return { __type = "bytes", _data = raw_str or "" }
end
-- 驗證並提取底層二進位字串：
-- allow_ascii = false -> 僅接受 bytes / bytearray / memoryview (供 encode 使用)
-- allow_ascii = true -> 額外接受純 ASCII str (供 decode 使用)
function b64_helper.extract_bytes(obj, allow_ascii)
local Runtime = require("Module:沙盒/a2569875/PythonScript/Runtime")
if type(obj) == "table" and obj.__type == "instance" and obj.__builtin_value ~= nil then
obj = obj.__builtin_value
end
if type(obj) == "table" then
local pt = obj.__type
if pt == "bytes" or pt == "bytearray" then
return obj._data
elseif pt == "memoryview" then
if obj._released then
Runtime.raise("ValueError", "operation forbidden on released memoryview object")
end
return obj._data
end
elseif type(obj) == "string" then
-- 維基特化語法糖：encode 時 (allow_ascii=false) 亦無條件放行字串
-- decode 時 (allow_ascii=true) 則維持原本的純 ASCII 安全檢查
if allow_ascii and obj:find("[\128-\255]") then
Runtime.raise("ValueError", "string argument should contain only ASCII characters")
end
return obj
end
local tname = type(obj)
if tname == "string" then tname = "str"
elseif tname == "boolean" then tname = "bool"
elseif tname == "number" then tname = (math.floor(obj) == obj) and "int" or "float"
elseif tname == "table" then tname = (obj.__class and obj.__class.__name) or obj.__type or "object" end
Runtime.raise("TypeError", "a bytes-like object is required, not '" .. tostring(tname) .. "'")
end
-- ==========================================
-- 3. Base64 核心編解碼 (含 altchars / urlsafe / validate)
-- ==========================================
function b64_helper.raw_b64encode(s, alphabet)
local alpha = alphabet or b64_helper.chars.b64
local out, n = {}, #s
local i = 1
while i <= n - 2 do
local b1, b2, b3 = string.byte(s, i, i + 2)
local v = b1 * 65536 + b2 * 256 + b3
local c1 = math.floor(v / 262144) + 1
local c2 = (math.floor(v / 4096) % 64) + 1
local c3 = (math.floor(v / 64) % 64) + 1
local c4 = (v % 64) + 1
out[#out + 1] = alpha:sub(c1, c1) .. alpha:sub(c2, c2) .. alpha:sub(c3, c3) .. alpha:sub(c4, c4)
i = i + 3
end
local rem = n - i + 1
if rem == 1 then
local b1 = string.byte(s, i)
local c1 = math.floor(b1 / 4) + 1
local c2 = ((b1 % 4) * 16) + 1
out[#out + 1] = alpha:sub(c1, c1) .. alpha:sub(c2, c2) .. "=="
elseif rem == 2 then
local b1, b2 = string.byte(s, i, i + 1)
local v = b1 * 256 + b2
local c1 = math.floor(v / 1024) + 1
local c2 = (math.floor(v / 16) % 64) + 1
local c3 = ((v % 16) * 4) + 1
out[#out + 1] = alpha:sub(c1, c1) .. alpha:sub(c2, c2) .. alpha:sub(c3, c3) .. "="
end
return table.concat(out)
end
function b64_helper.raw_b64decode(s, altchars, validate)
local alpha = b64_helper.chars.b64
if altchars then
if #altchars ~= 2 then
require("Module:沙盒/a2569875/PythonScript/Runtime").raise("ValueError", "altchars must be a length-2 bytes-like object")
end
alpha = alpha:sub(1, 62) .. altchars
end
local inv = (alpha == b64_helper.chars.b64) and b64_helper.get_inv_map("b64")
or (alpha == b64_helper.chars.b64url and b64_helper.get_inv_map("b64url"))
or b64_helper.get_inv_map(alpha, alpha)
local clean = {}
for i = 1, #s do
local b = string.byte(s, i)
if inv[b] ~= nil or b == 61 then -- 61 is '='
clean[#clean + 1] = string.char(b)
elseif validate then
b64_helper.raise_error("Non-base64 digit found")
end
end
local cs = table.concat(clean)
local clen = #cs
if clen == 0 then return "" end
if validate and (clen % 4 ~= 0) then
b64_helper.raise_error("Incorrect padding")
end
-- 剝除尾端 '=' 並檢查有效資料字元數
local data_str = cs:match("^(.-)=*$") or cs
if data_str:find("=", 1, true) then
if validate then b64_helper.raise_error("Discontinuous padding not allowed") end
data_str = data_str:gsub("=", "")
end
local dlen = #data_str
local rem = dlen % 4
if rem == 1 then
b64_helper.raise_error("Invalid base64-encoded string: number of data characters (" .. dlen .. ") cannot be 1 more than a multiple of 4")
end
if rem > 0 and (#cs - dlen) < (4 - rem) and validate then
b64_helper.raise_error("Incorrect padding")
end
local out = {}
local i = 1
while i <= dlen - 3 do
local v1, v2, v3, v4 = inv[string.byte(data_str, i)], inv[string.byte(data_str, i+1)], inv[string.byte(data_str, i+2)], inv[string.byte(data_str, i+3)]
local n = v1 * 262144 + v2 * 4096 + v3 * 64 + v4
out[#out + 1] = string.char(math.floor(n / 65536), math.floor(n / 256) % 256, n % 256)
i = i + 4
end
if rem == 2 then
local v1, v2 = inv[string.byte(data_str, i)], inv[string.byte(data_str, i+1)]
local n = v1 * 64 + v2
out[#out + 1] = string.char(math.floor(n / 16))
elseif rem == 3 then
local v1, v2, v3 = inv[string.byte(data_str, i)], inv[string.byte(data_str, i+1)], inv[string.byte(data_str, i+2)]
local n = v1 * 4096 + v2 * 64 + v3
out[#out + 1] = string.char(math.floor(n / 1024), math.floor(n / 4) % 256)
end
return table.concat(out)
end
-- ==========================================
-- 4. Base32 / Base32hex 核心編解碼
-- ==========================================
function b64_helper.raw_b32encode(s, is_hex)
local alpha = is_hex and b64_helper.chars.b32hex or b64_helper.chars.b32
local out, n = {}, #s
local i = 1
while i <= n do
local rem = n - i + 1
local b1 = string.byte(s, i) or 0
local b2 = (rem >= 2) and string.byte(s, i + 1) or 0
local b3 = (rem >= 3) and string.byte(s, i + 2) or 0
local b4 = (rem >= 4) and string.byte(s, i + 3) or 0
local b5 = (rem >= 5) and string.byte(s, i + 4) or 0
-- 40-bit 精確整數運算
local v = (((b1 * 256 + b2) * 256 + b3) * 256 + b4) * 256 + b5
local c = {}
for k = 8, 1, -1 do
local idx = (v % 32) + 1
c[k] = alpha:sub(idx, idx)
v = math.floor(v / 32)
end
if rem == 1 then
out[#out + 1] = c[1] .. c[2] .. "======"
elseif rem == 2 then
out[#out + 1] = c[1] .. c[2] .. c[3] .. c[4] .. "===="
elseif rem == 3 then
out[#out + 1] = c[1] .. c[2] .. c[3] .. c[4] .. c[5] .. "==="
elseif rem == 4 then
out[#out + 1] = c[1] .. c[2] .. c[3] .. c[4] .. c[5] .. c[6] .. c[7] .. "="
else
out[#out + 1] = table.concat(c)
end
i = i + 5
end
return table.concat(out)
end
function b64_helper.raw_b32decode(s, is_hex, casefold, map01)
if (#s % 8) ~= 0 then
b64_helper.raise_error("Incorrect padding")
end
if casefold then s = s:upper() end
if not is_hex and map01 then
if #map01 ~= 1 then
require("Module:沙盒/a2569875/PythonScript/Runtime").raise("ValueError", "map01 must be a 1-character string or bytes")
end
local repl1 = casefold and map01:upper() or map01
s = s:gsub("0", "O"):gsub("1", repl1)
end
local inv = b64_helper.get_inv_map(is_hex and "b32hex" or "b32")
local n = #s
if n == 0 then return "" end
local out = {}
for i = 1, n, 8 do
local chunk = s:sub(i, i + 7)
local pad_start = chunk:find("=", 1, true)
local pad_len = 0
if pad_start then
if i + 7 < n or not chunk:sub(pad_start):match("^=+$") then
b64_helper.raise_error("Incorrect padding")
end
pad_len = 8 - pad_start + 1
if pad_len ~= 1 and pad_len ~= 3 and pad_len ~= 4 and pad_len ~= 6 then
b64_helper.raise_error("Incorrect padding")
end
end
local v = 0
for k = 1, 8 do
if pad_start and k >= pad_start then
v = v * 32
else
local d = inv[string.byte(chunk, k)]
if d == nil then b64_helper.raise_error("Non-base32 digit found") end
v = v * 32 + d
end
end
local bytes = {}
for k = 5, 1, -1 do
bytes[k] = string.char(v % 256)
v = math.floor(v / 256)
end
local keep = (pad_len == 0 and 5) or (pad_len == 1 and 4) or (pad_len == 3 and 3) or (pad_len == 4 and 2) or 1
out[#out + 1] = table.concat(bytes, "", 1, keep)
end
return table.concat(out)
end
-- ==========================================
-- 5. Base16 核心編解碼
-- ==========================================
function b64_helper.raw_b16encode(s)
local alpha = b64_helper.chars.b16
local out = {}
for i = 1, #s do
local b = string.byte(s, i)
local hi = math.floor(b / 16) + 1
local lo = (b % 16) + 1
out[i] = alpha:sub(hi, hi) .. alpha:sub(lo, lo)
end
return table.concat(out)
end
function b64_helper.raw_b16decode(s, casefold)
if (#s % 2) ~= 0 then
b64_helper.raise_error("Odd-length string")
end
if casefold then s = s:upper() end
local inv = b64_helper.get_inv_map("b16")
local out = {}
for i = 1, #s, 2 do
local hi = inv[string.byte(s, i)]
local lo = inv[string.byte(s, i + 1)]
if hi == nil or lo == nil then
b64_helper.raise_error("Non-base16 digit found")
end
out[#out + 1] = string.char(hi * 16 + lo)
end
return table.concat(out)
end
-- ==========================================
-- 6. Ascii85 / Base85 / Z85 核心編解碼
-- ==========================================
-- 將 32-bit 無號整數轉為 5 個 85 進位字元
function b64_helper.u32_to_85(v, alpha)
local c5 = (v % 85) + 1; v = math.floor(v / 85)
local c4 = (v % 85) + 1; v = math.floor(v / 85)
local c3 = (v % 85) + 1; v = math.floor(v / 85)
local c2 = (v % 85) + 1
local c1 = math.floor(v / 85) + 1
return alpha:sub(c1, c1) .. alpha:sub(c2, c2) .. alpha:sub(c3, c3) .. alpha:sub(c4, c4) .. alpha:sub(c5, c5)
end
function b64_helper.raw_a85encode(s, foldspaces, wrapcol, pad, adobe)
local alpha = b64_helper.chars.a85
local out, n = {}, #s
local i = 1
while i <= n - 3 do
local b1, b2, b3, b4 = string.byte(s, i, i + 3)
local v = ((b1 * 256 + b2) * 256 + b3) * 256 + b4
if v == 0 then
out[#out + 1] = "z"
elseif foldspaces and v == 0x20202020 then
out[#out + 1] = "y"
else
out[#out + 1] = b64_helper.u32_to_85(v, alpha)
end
i = i + 4
end
local rem = n - i + 1
if rem > 0 then
local b1 = string.byte(s, i) or 0
local b2 = (rem >= 2) and string.byte(s, i + 1) or 0
local b3 = (rem >= 3) and string.byte(s, i + 2) or 0
local v = ((b1 * 256 + b2) * 256 + b3) * 256
local block = b64_helper.u32_to_85(v, alpha)
out[#out + 1] = pad and block or block:sub(1, rem + 1)
end
local res = table.concat(out)
if adobe then res = "<~" .. res .. "~>" end
if wrapcol and wrapcol > 0 then
local lines = {}
for j = 1, #res, wrapcol do
lines[#lines + 1] = res:sub(j, j + wrapcol - 1)
end
res = table.concat(lines, "\n")
end
return res
end
function b64_helper.raw_a85decode(s, foldspaces, adobe, ignorechars)
local Runtime = require("Module:沙盒/a2569875/PythonScript/Runtime")
if adobe then
if s:sub(-2) ~= "~>" then
Runtime.raise("ValueError", "Ascii85 encoded byte sequence must end with '~>'")
end
if s:sub(1, 2) == "<~" then s = s:sub(3, -3) else s = s:sub(1, -3) end
end
local ign = {}
local ign_str = ignorechars or " \t\n\r\v"
for i = 1, #ign_str do ign[string.byte(ign_str, i)] = true end
local inv = b64_helper.get_inv_map("a85")
local out, group = {}, {}
for i = 1, #s do
local b = string.byte(s, i)
if not ign[b] then
if b == 122 then -- 'z'
if #group > 0 then Runtime.raise("ValueError", "'z' inside Ascii85 5-tuple") end
out[#out + 1] = "\0\0\0\0"
elseif foldspaces and b == 121 then -- 'y'
if #group > 0 then Runtime.raise("ValueError", "'y' inside Ascii85 5-tuple") end
out[#out + 1] = " "
else
local d = inv[b]
if d == nil then
Runtime.raise("ValueError", "Non-Ascii85 digit found: " .. string.char(b))
end
group[#group + 1] = d
if #group == 5 then
local v = (((group[1] * 85 + group[2]) * 85 + group[3]) * 85 + group[4]) * 85 + group[5]
if v > 4294967295 then Runtime.raise("ValueError", "Ascii85 overflow") end
out[#out + 1] = string.char(
math.floor(v / 16777216) % 256,
math.floor(v / 65536) % 256,
math.floor(v / 256) % 256,
v % 256
)
group = {}
end
end
end
end
local rem = #group
if rem == 1 then
Runtime.raise("ValueError", "Final Ascii85 group cannot have length 1")
elseif rem > 1 then
for k = rem + 1, 5 do group[k] = 84 end
local v = (((group[1] * 85 + group[2]) * 85 + group[3]) * 85 + group[4]) * 85 + group[5]
if v > 4294967295 then Runtime.raise("ValueError", "Ascii85 overflow") end
local b4 = string.char(
math.floor(v / 16777216) % 256,
math.floor(v / 65536) % 256,
math.floor(v / 256) % 256,
v % 256
)
out[#out + 1] = b4:sub(1, rem - 1)
end
return table.concat(out)
end
function b64_helper.raw_b85_or_z85_encode(s, mode, pad)
local alpha = b64_helper.chars[mode]
local out, n = {}, #s
local i = 1
while i <= n - 3 do
local b1, b2, b3, b4 = string.byte(s, i, i + 3)
local v = ((b1 * 256 + b2) * 256 + b3) * 256 + b4
out[#out + 1] = b64_helper.u32_to_85(v, alpha)
i = i + 4
end
local rem = n - i + 1
if rem > 0 then
local b1 = string.byte(s, i) or 0
local b2 = (rem >= 2) and string.byte(s, i + 1) or 0
local b3 = (rem >= 3) and string.byte(s, i + 2) or 0
local v = ((b1 * 256 + b2) * 256 + b3) * 256
local block = b64_helper.u32_to_85(v, alpha)
out[#out + 1] = pad and block or block:sub(1, rem + 1)
end
return table.concat(out)
end
function b64_helper.raw_b85_or_z85_decode(s, mode)
local Runtime = require("Module:沙盒/a2569875/PythonScript/Runtime")
local inv = b64_helper.get_inv_map(mode)
local out, n = {}, #s
local rem = n % 5
if rem == 1 then
Runtime.raise("ValueError", "Invalid " .. mode .. " string length: cannot be 1 more than a multiple of 5")
end
local i = 1
while i <= n do
local chunk_len = math.min(5, n - i + 1)
local v = 0
for k = 0, 4 do
local d
if k < chunk_len then
d = inv[string.byte(s, i + k)]
if d == nil then
Runtime.raise("ValueError", "Bad " .. mode .. " character at position " .. (i + k - 1))
end
else
d = 84
end
v = v * 85 + d
end
if v > 4294967295 then
Runtime.raise("ValueError", mode .. " overflow in hunk starting at byte " .. (i - 1))
end
local b4 = string.char(
math.floor(v / 16777216) % 256,
math.floor(v / 65536) % 256,
math.floor(v / 256) % 256,
v % 256
)
out[#out + 1] = (chunk_len == 5) and b4 or b4:sub(1, chunk_len - 1)
i = i + 5
end
return table.concat(out)
end
-- ==========================================
-- 7. Python base64 與 binascii 模組工廠
-- ==========================================
function b64_helper.get_base64_module()
b64_helper.ensure_exceptions()
local PyClass = require("Module:沙盒/a2569875/PythonScript/Class")
local B = require("Module:沙盒/a2569875/PythonScript/Runtime").builtins
local function fn(name, f)
return { __type = "builtin_method", __name = name, __call = f }
end
local dict = {
b64encode = fn("b64encode", function(a, kw)
local s = b64_helper.extract_bytes(a[1], false)
local alt = (a[2] ~= nil and a[2]) or (kw and kw.altchars)
local alpha = b64_helper.chars.b64
if not b64_helper.is_none(alt) then
local alt_s = b64_helper.extract_bytes(alt, false)
if #alt_s ~= 2 then require("Module:沙盒/a2569875/PythonScript/Runtime").raise("ValueError", "altchars must be a length-2 bytes-like object") end
alpha = alpha:sub(1, 62) .. alt_s
end
return b64_helper.make_bytes(b64_helper.raw_b64encode(s, alpha))
end),
b64decode = fn("b64decode", function(a, kw)
local s = b64_helper.extract_bytes(a[1], true)
local alt = (a[2] ~= nil and a[2]) or (kw and kw.altchars)
local val_flag = (a[3] ~= nil and a[3]) or (kw and kw.validate) or false
local alt_s = not b64_helper.is_none(alt) and b64_helper.extract_bytes(alt, true) or nil
return b64_helper.make_bytes(b64_helper.raw_b64decode(s, alt_s, B.bool.__call({val_flag})))
end),
standard_b64encode = fn("standard_b64encode", function(a)
local s = b64_helper.extract_bytes(a[1], false)
return b64_helper.make_bytes(b64_helper.raw_b64encode(s, b64_helper.chars.b64))
end),
standard_b64decode = fn("standard_b64decode", function(a)
local s = b64_helper.extract_bytes(a[1], true)
return b64_helper.make_bytes(b64_helper.raw_b64decode(s, nil, false))
end),
urlsafe_b64encode = fn("urlsafe_b64encode", function(a)
local s = b64_helper.extract_bytes(a[1], false)
return b64_helper.make_bytes(b64_helper.raw_b64encode(s, b64_helper.chars.b64url))
end),
urlsafe_b64decode = fn("urlsafe_b64decode", function(a)
local s = b64_helper.extract_bytes(a[1], true)
return b64_helper.make_bytes(b64_helper.raw_b64decode(s, "-_", false))
end),
b32encode = fn("b32encode", function(a)
local s = b64_helper.extract_bytes(a[1], false)
return b64_helper.make_bytes(b64_helper.raw_b32encode(s, false))
end),
b32decode = fn("b32decode", function(a, kw)
local s = b64_helper.extract_bytes(a[1], true)
local cf = (a[2] ~= nil and a[2]) or (kw and kw.casefold) or false
local m01 = (a[3] ~= nil and a[3]) or (kw and kw.map01)
local m01_s = not b64_helper.is_none(m01) and b64_helper.extract_bytes(m01, true) or nil
return b64_helper.make_bytes(b64_helper.raw_b32decode(s, false, B.bool.__call({cf}), m01_s))
end),
b32hexencode = fn("b32hexencode", function(a)
local s = b64_helper.extract_bytes(a[1], false)
return b64_helper.make_bytes(b64_helper.raw_b32encode(s, true))
end),
b32hexdecode = fn("b32hexdecode", function(a, kw)
local s = b64_helper.extract_bytes(a[1], true)
local cf = (a[2] ~= nil and a[2]) or (kw and kw.casefold) or false
return b64_helper.make_bytes(b64_helper.raw_b32decode(s, true, B.bool.__call({cf}), nil))
end),
b16encode = fn("b16encode", function(a)
local s = b64_helper.extract_bytes(a[1], false)
return b64_helper.make_bytes(b64_helper.raw_b16encode(s))
end),
b16decode = fn("b16decode", function(a, kw)
local s = b64_helper.extract_bytes(a[1], true)
local cf = (a[2] ~= nil and a[2]) or (kw and kw.casefold) or false
return b64_helper.make_bytes(b64_helper.raw_b16decode(s, B.bool.__call({cf})))
end),
a85encode = fn("a85encode", function(a, kw)
local s = b64_helper.extract_bytes(a[1], false)
kw = kw or {}
local fs = B.bool.__call({kw.foldspaces or false})
local wc = tonumber(kw.wrapcol) or 0
local pad = B.bool.__call({kw.pad or false})
local adobe = B.bool.__call({kw.adobe or false})
return b64_helper.make_bytes(b64_helper.raw_a85encode(s, fs, wc, pad, adobe))
end),
a85decode = fn("a85decode", function(a, kw)
local s = b64_helper.extract_bytes(a[1], true)
kw = kw or {}
local fs = B.bool.__call({kw.foldspaces or false})
local adobe = B.bool.__call({kw.adobe or false})
local ign = not b64_helper.is_none(kw.ignorechars) and b64_helper.extract_bytes(kw.ignorechars, false) or " \t\n\r\v"
return b64_helper.make_bytes(b64_helper.raw_a85decode(s, fs, adobe, ign))
end),
b85encode = fn("b85encode", function(a, kw)
local s = b64_helper.extract_bytes(a[1], false)
local pad = (a[2] ~= nil and a[2]) or (kw and kw.pad) or false
return b64_helper.make_bytes(b64_helper.raw_b85_or_z85_encode(s, "b85", B.bool.__call({pad})))
end),
b85decode = fn("b85decode", function(a)
local s = b64_helper.extract_bytes(a[1], true)
return b64_helper.make_bytes(b64_helper.raw_b85_or_z85_decode(s, "b85"))
end),
z85encode = fn("z85encode", function(a)
local s = b64_helper.extract_bytes(a[1], false)
return b64_helper.make_bytes(b64_helper.raw_b85_or_z85_encode(s, "z85", false))
end),
z85decode = fn("z85decode", function(a)
local s = b64_helper.extract_bytes(a[1], true)
return b64_helper.make_bytes(b64_helper.raw_b85_or_z85_decode(s, "z85"))
end),
encodebytes = fn("encodebytes", function(a)
local s = b64_helper.extract_bytes(a[1], false)
if #s == 0 then return b64_helper.make_bytes("") end
local chunks = {}
for i = 1, #s, 57 do
chunks[#chunks + 1] = b64_helper.raw_b64encode(s:sub(i, i + 56), b64_helper.chars.b64) .. "\n"
end
return b64_helper.make_bytes(table.concat(chunks))
end),
decodebytes = fn("decodebytes", function(a)
local s = b64_helper.extract_bytes(a[1], false)
return b64_helper.make_bytes(b64_helper.raw_b64decode(s, nil, false))
end)
}
local mod = PyClass.make_instance(PyClass.make_class("module", {}, {}))
for k, v in pairs(dict) do mod.__dict[k] = v end
mod.__dict["__name__"] = "base64"
return mod
end
function b64_helper.get_binascii_module()
b64_helper.ensure_exceptions()
local PyClass = require("Module:沙盒/a2569875/PythonScript/Class")
local B = require("Module:沙盒/a2569875/PythonScript/Runtime").builtins
local bit32 = require("bit32")
local function fn(name, f)
return { __type = "builtin_method", __name = name, __call = f }
end
local hexlify_fn = fn("hexlify", function(a, kw)
local s = b64_helper.extract_bytes(a[1], false)
local sep = (a[2] ~= nil and a[2]) or (kw and kw.sep)
local hex_lower = b64_helper.raw_b16encode(s):lower()
if not b64_helper.is_none(sep) then
local sep_s = (type(sep) == "string") and sep or b64_helper.extract_bytes(sep, true)
if #sep_s ~= 1 then require("Module:沙盒/a2569875/PythonScript/Runtime").raise("ValueError", "sep must be length 1") end
local parts = {}
for i = 1, #hex_lower, 2 do parts[#parts + 1] = hex_lower:sub(i, i + 1) end
hex_lower = table.concat(parts, sep_s)
end
return b64_helper.make_bytes(hex_lower)
end)
local unhexlify_fn = fn("unhexlify", function(a)
local s = b64_helper.extract_bytes(a[1], true)
return b64_helper.make_bytes(b64_helper.raw_b16decode(s, true))
end)
local b2a_base64_fn = fn("b2a_base64", function(a, kw)
local s = b64_helper.extract_bytes(a[1], false)
local nl = true
if kw and kw.newline ~= nil then nl = B.bool.__call({kw.newline}) end
local res = b64_helper.raw_b64encode(s, b64_helper.chars.b64)
return b64_helper.make_bytes(nl and (res .. "\n") or res)
end)
local a2b_base64_fn = fn("a2b_base64", function(a)
local s = b64_helper.extract_bytes(a[1], true)
return b64_helper.make_bytes(b64_helper.raw_b64decode(s, nil, false))
end)
local crc32_fn = fn("crc32", function(a)
local s = b64_helper.extract_bytes(a[1], false)
local crc = bit32.bnot(tonumber(a[2]) or 0)
for i = 1, #s do
crc = bit32.bxor(crc, string.byte(s, i))
for _ = 1, 8 do
local mask = -(bit32.band(crc, 1))
crc = bit32.bxor(bit32.rshift(crc, 1), bit32.band(0xEDB88320, mask))
end
end
return bit32.bnot(crc)
end)
local dict = {
Error = b64_helper.ErrorClass,
Incomplete = b64_helper.IncompleteClass,
hexlify = hexlify_fn,
b2a_hex = hexlify_fn,
unhexlify = unhexlify_fn,
a2b_hex = unhexlify_fn,
b2a_base64 = b2a_base64_fn,
a2b_base64 = a2b_base64_fn,
crc32 = crc32_fn
}
local mod = PyClass.make_instance(PyClass.make_class("module", {}, {}))
for k, v in pairs(dict) do mod.__dict[k] = v end
mod.__dict["__name__"] = "binascii"
return mod
end
return b64_helper
end
-- ==========================================
-- 2. fractions 有理數演算法
-- ==========================================
function StdAlgorithms.fractions()
local fractions_helper = {
initialized = false,
cache = {}
}
-- ==========================================
-- 1. 大數 (BigInt) 與基礎整數運算橋接器
-- ==========================================
function fractions_helper.is_none(v)
return v == nil or (type(v) == "table" and v.__class and v.__class.__name == "NoneType")
end
function fractions_helper.is_fraction(v)
return type(v) == "table" and v.__type == "instance" and v.__dict and v.__dict._is_fraction == true
end
function fractions_helper.is_decimal(v)
return type(v) == "table" and v.__type == "instance" and v.__dict and v.__dict._is_decimal == true
end
function fractions_helper.is_int(v)
if type(v) == "boolean" then return true end
if type(v) == "number" then return math.floor(v) == v and math.abs(v) <= 9007199254740990 end
if type(v) == "table" and v.__type == "int" then return true end
return false
end
function fractions_helper.int_zero(a)
if type(a) == "boolean" then return not a end
if type(a) == "number" then return a == 0 end
if type(a) == "table" and a.__type == "int" then
return #a.limbs == 1 and a.limbs[1] == 0
end
return false
end
function fractions_helper.int_sign(a)
if fractions_helper.int_zero(a) then return 0 end
if type(a) == "boolean" then return a and 1 or 0 end
if type(a) == "number" then return a < 0 and -1 or 1 end
if type(a) == "table" and a.__type == "int" then return a.sign end
return 1
end
function fractions_helper.int_neg(a)
if type(a) == "boolean" then a = a and 1 or 0 end
if fractions_helper.int_zero(a) then return 0 end
if type(a) == "number" then return -a end
if type(a) == "table" and a.__type == "int" then
return { __type = "int", is_big = true, value = a.value and -a.value or nil, sign = -a.sign, limbs = a.limbs }
end
return 0
end
function fractions_helper.int_abs(a)
if type(a) == "boolean" then return a and 1 or 0 end
if fractions_helper.int_sign(a) < 0 then return fractions_helper.int_neg(a) end
return a
end
function fractions_helper.int_op(a, b, op)
if type(a) == "boolean" then a = a and 1 or 0 end
if type(b) == "boolean" then b = b and 1 or 0 end
if type(a) == "number" and type(b) == "number" then
local res
if op == "+" then res = a + b
elseif op == "-" then res = a - b
elseif op == "*" then res = a * b
elseif op == "//" then res = math.floor(a / b)
elseif op == "%" then res = a % b end
if res and math.abs(res) <= 9007199254740990 then return res end
end
local Evaluator = require("Module:沙盒/a2569875/PythonScript/Evaluator")
return Evaluator.bigint_op(a, b, op)
end
function fractions_helper.int_cmp(a, b)
if type(a) == "boolean" then a = a and 1 or 0 end
if type(b) == "boolean" then b = b and 1 or 0 end
if type(a) == "number" and type(b) == "number" then
if a < b then return -1 elseif a > b then return 1 else return 0 end
end
return require("Module:沙盒/a2569875/PythonScript/Evaluator/Utils").py_cmp(a, b)
end
-- 支援任意精度 BigInt 的最大公因數 (GCD)
function fractions_helper.int_gcd(a, b)
a = fractions_helper.int_abs(a)
b = fractions_helper.int_abs(b)
if type(a) == "number" and type(b) == "number" then
while b ~= 0 do a, b = b, a % b end
return a
end
local BigInt = require("Module:沙盒/a2569875/PythonScript/Runtime/Cmath").BigInt
local la, lb = BigInt.to_limbs(a), BigInt.to_limbs(b)
while not (#lb == 1 and lb[1] == 0) do
local _, r = BigInt.divmod_limbs(la, lb)
la, lb = lb, r
end
if #la == 1 and la[1] == 0 then return 0 end
local s = BigInt.to_string(1, la)
local n = tonumber(s)
if n and n <= BigInt.SAFE_LIMIT then return n end
return { __type = "int", is_big = true, value = n, sign = 1, limbs = la }
end
function fractions_helper.pow10(exp)
if exp <= 0 then return 1 end
if exp <= 15 then return 10 ^ exp end
return require("Module:沙盒/a2569875/PythonScript/Runtime").builtins.int.__call({ "1" .. string.rep("0", exp) })
end
-- 將分子與分母約分並正規化分母為正整數
function fractions_helper.normalize_nd(num, den)
local Runtime = require("Module:沙盒/a2569875/PythonScript/Runtime")
if fractions_helper.int_zero(den) then
Runtime.raise("ZeroDivisionError", "Fraction(" .. tostring(num) .. ", 0)")
end
if fractions_helper.int_zero(num) then
return 0, 1
end
if fractions_helper.int_sign(den) < 0 then
num = fractions_helper.int_neg(num)
den = fractions_helper.int_neg(den)
end
local g = fractions_helper.int_gcd(num, den)
if g ~= 1 and not (type(g) == "table" and #g.limbs == 1 and g.limbs[1] == 1) then
num = fractions_helper.int_op(num, g, "//")
den = fractions_helper.int_op(den, g, "//")
end
return num, den
end
-- ==========================================
-- 2. 循環小數自動識別與字串/數值轉分數核心
-- ==========================================
-- 偵測小數點後字串 frac 是否含有循環節 (回傳 prefix_str, period_str)
function fractions_helper.detect_repeating_period(frac, is_from_float)
local len = #frac
if len < 6 then return nil, nil end
-- 若末尾全為 0，屬於有限小數
if frac:match("^0+$") then return nil, nil end
local max_prefix = math.min(4, len - 6)
for a = 0, max_prefix do
local sub = frac:sub(a + 1)
local slen = #sub
local max_p = math.floor(slen / 2)
for p = 1, max_p do
local pat = sub:sub(1, p)
-- 排除全為 0 的偽週期，以及對 float 結尾全為 9 的誤差進行處理
if not pat:match("^0+$") then
local min_reps = (p == 1 and 6) or (p == 2 and 3) or 2
local reps = math.floor(slen / p)
local rem = slen % p
-- 字串輸入要求完整重複 (rem == 0)，或是總長 >= 10 時允許尾端截斷匹配循環節前綴
if reps >= min_reps and (rem == 0 or is_from_float or slen >= 10) then
local ok = true
for r = 1, reps - 1 do
if sub:sub(r * p + 1, (r + 1) * p) ~= pat then
ok = false; break
end
end
if ok and rem > 0 then
local tail = sub:sub(reps * p + 1)
local expected_tail = pat:sub(1, rem)
if tail ~= expected_tail then
-- 容許 float 最末位因四捨五入差 1 (例如 0.16666666666666666 或 0.6666667)
local t_num, e_num = tonumber(tail), tonumber(expected_tail)
if not (is_from_float and t_num and e_num and math.abs(t_num - e_num) <= 1) then
ok = false
end
end
end
if ok then
return frac:sub(1, a), pat
end
end
end
end
end
return nil, nil
end
-- 將整數部分、小數部分與指數轉為 (num, den)，支援自動識別循環小數
function fractions_helper.parse_decimal_to_nd(sign, int_part, frac_part, exp_val, is_from_float)
local B = require("Module:沙盒/a2569875/PythonScript/Runtime").builtins
int_part = (int_part == "" or not int_part) and "0" or int_part
frac_part = frac_part or ""
exp_val = exp_val or 0
-- 1. 檢查顯式括號循環節語法，如 0.(142857) 或 0.1(6)
local pre_paren, in_paren = frac_part:match("^(%d*)%((%d+)%)$")
-- 2. 若無括號，啟動智慧循環節偵測 (如 0.142857142857 -> prefix="", period="142857")
if not in_paren then
pre_paren, in_paren = fractions_helper.detect_repeating_period(frac_part, is_from_float)
end
local num, den
if in_paren and #in_paren > 0 then
local a_len = #pre_paren
local p_len = #in_paren
local ap_int = B.int.__call({ (pre_paren .. in_paren == "") and "0" or (pre_paren .. in_paren) })
local a_int = (a_len > 0) and B.int.__call({ pre_paren }) or 0
local frac_num = fractions_helper.int_op(ap_int, a_int, "-")
local nines = B.int.__call({ string.rep("9", p_len) })
local frac_den = fractions_helper.int_op(fractions_helper.pow10(a_len), nines, "*")
local i_int = B.int.__call({ int_part })
num = fractions_helper.int_op(fractions_helper.int_op(i_int, frac_den, "*"), frac_num, "+")
den = frac_den
else
-- 一般有限小數
local combined = int_part .. frac_part
combined = combined:gsub("^0+", "")
if combined == "" then return 0, 1 end
num = B.int.__call({ combined })
den = fractions_helper.pow10(#frac_part)
end
if exp_val > 0 then
num = fractions_helper.int_op(num, fractions_helper.pow10(exp_val), "*")
elseif exp_val < 0 then
den = fractions_helper.int_op(den, fractions_helper.pow10(-exp_val), "*")
end
if sign < 0 then num = fractions_helper.int_neg(num) end
return fractions_helper.normalize_nd(num, den)
end
-- 解析字串為 (num, den)
function fractions_helper.parse_string(str)
local Runtime = require("Module:沙盒/a2569875/PythonScript/Runtime")
local B = Runtime.builtins
local s = str:match("^%s*(.-)%s*$")
if s == "" then
Runtime.raise("ValueError", "Invalid literal for Fraction: '" .. str .. "'")
end
if s:find("__", 1, true) or s:sub(1, 1) == "_" or s:sub(-1) == "_" then
Runtime.raise("ValueError", "Invalid literal for Fraction: '" .. str .. "'")
end
s = s:gsub("(%d)_(%d)", "%1%2"):gsub("(%d)_(%d)", "%1%2")
-- 分數格式: "a/b"
local num_s, den_s = s:match("^([%+%-]?%d+)%s*/%s*([%+%-]?%d+)$")
if num_s and den_s then
local n = B.int.__call({ num_s })
local d = B.int.__call({ den_s })
return fractions_helper.normalize_nd(n, d)
end
local sign = 1
if s:sub(1, 1) == "-" then sign = -1; s = s:sub(2)
elseif s:sub(1, 1) == "+" then s = s:sub(2) end
-- 支援結尾省略號如 "0.142857142857..."
s = s:gsub("%.%.%.$", "")
local mantissa, exp_part = s:match("^([^eE]+)[eE]([%.%+%-]?%d+)$")
local exp_val = 0
if mantissa then
exp_val = tonumber(exp_part)
if not exp_val or math.floor(exp_val) ~= exp_val then
Runtime.raise("ValueError", "Invalid literal for Fraction: '" .. str .. "'")
end
s = mantissa
end
local int_p, frac_p
if s:find("%.", 1, false) then
int_p, frac_p = s:match("^(%d*)%.([%d%(%)]*)$")
if not int_p or (int_p == "" and frac_p == "") then
Runtime.raise("ValueError", "Invalid literal for Fraction: '" .. str .. "'")
end
else
if not s:match("^%d+$") then
Runtime.raise("ValueError", "Invalid literal for Fraction: '" .. str .. "'")
end
int_p, frac_p = s, ""
end
return fractions_helper.parse_decimal_to_nd(sign, int_p, frac_p, exp_val, false)
end
-- 解析任意單一物件為 (num, den)
function fractions_helper.coerce_single(val)
local Runtime = require("Module:沙盒/a2569875/PythonScript/Runtime")
if fractions_helper.is_none(val) then return 0, 1 end
if fractions_helper.is_fraction(val) then
return val.__dict._num, val.__dict._den
end
if fractions_helper.is_int(val) then
if type(val) == "boolean" then return val and 1 or 0, 1 end
return val, 1
end
if type(val) == "number" then
if val ~= val then Runtime.raise("ValueError", "Cannot convert NaN to Fraction.") end
if val == math.huge or val == -math.huge then Runtime.raise("OverflowError", "Cannot convert Infinity to Fraction.") end
-- 將 float 轉為十進位字串並交由循環小數偵測引擎處理
local sign = val < 0 and -1 or 1
local s = string.format("%.14g", math.abs(val))
return fractions_helper.parse_string((sign < 0 and "-" or "") .. s)
end
if fractions_helper.is_decimal(val) then
local d = val.__dict
if d.special == "Inf" then Runtime.raise("OverflowError", "Cannot convert Infinity to Fraction.") end
if d.special then Runtime.raise("ValueError", "Cannot convert NaN to Fraction.") end
local s = require("Module:沙盒/a2569875/PythonScript/Runtime").builtins.str.__call({val})
return fractions_helper.parse_string(s)
end
if type(val) == "string" then
return fractions_helper.parse_string(val)
end
Runtime.raise("TypeError", "argument should be a string or a Rational instance")
end
-- ==========================================
-- 3. 連分數收斂與浮點數轉換輔助
-- ==========================================
function fractions_helper.limit_denominator_raw(num, den, max_den)
local Runtime = require("Module:沙盒/a2569875/PythonScript/Runtime")
if fractions_helper.int_cmp(max_den, 1) < 0 then
Runtime.raise("ValueError", "max_denominator should be at least 1")
end
if fractions_helper.int_cmp(den, max_den) <= 0 then
return num, den
end
local p0, q0, p1, q1 = 0, 1, 1, 0
local n, d = num, den
while true do
local a = fractions_helper.int_op(n, d, "//")
local q2 = fractions_helper.int_op(q0, fractions_helper.int_op(a, q1, "*"), "+")
if fractions_helper.int_cmp(q2, max_den) > 0 then break end
local p2 = fractions_helper.int_op(p0, fractions_helper.int_op(a, p1, "*"), "+")
p0, q0, p1, q1 = p1, q1, p2, q2
local r = fractions_helper.int_op(n, fractions_helper.int_op(a, d, "*"), "-")
n, d = d, r
if fractions_helper.int_zero(d) then break end
end
local k = fractions_helper.int_op(fractions_helper.int_op(max_den, q0, "-"), q1, "//")
local bound1_n = fractions_helper.int_op(p0, fractions_helper.int_op(k, p1, "*"), "+")
local bound1_d = fractions_helper.int_op(q0, fractions_helper.int_op(k, q1, "*"), "+")
-- 比較 |bound1 - self| 與 |p1/q1 - self|
local diff1_num = fractions_helper.int_abs(fractions_helper.int_op(
fractions_helper.int_op(bound1_n, den, "*"),
fractions_helper.int_op(num, bound1_d, "*"), "-"
))
local diff2_num = fractions_helper.int_abs(fractions_helper.int_op(
fractions_helper.int_op(p1, den, "*"),
fractions_helper.int_op(num, q1, "*"), "-"
))
local lhs = fractions_helper.int_op(diff2_num, bound1_d, "*")
local rhs = fractions_helper.int_op(diff1_num, q1, "*")
if fractions_helper.int_cmp(lhs, rhs) <= 0 then
return p1, q1
else
return bound1_n, bound1_d
end
end
function fractions_helper.to_float(self)
local n, d = self.__dict._num, self.__dict._den
if type(n) == "number" and type(d) == "number" then
return n / d
end
return require("Module:沙盒/a2569875/PythonScript/Evaluator").bigint_op(n, d, "/")
end
function fractions_helper.make_fraction(num, den)
fractions_helper.ensure_init()
local n, d = fractions_helper.normalize_nd(num, den)
local inst = require("Module:沙盒/a2569875/PythonScript/Class").make_instance(fractions_helper.cache.Fraction)
inst.__dict._is_fraction = true
inst.__dict._num = n
inst.__dict._den = d
return inst
end
-- ==========================================
-- 4. 供 math 模組呼叫的高精度輔助函式
-- ==========================================
function fractions_helper.math_floor(frac)
return fractions_helper.int_op(frac.__dict._num, frac.__dict._den, "//")
end
function fractions_helper.math_ceil(frac)
local neg_n = fractions_helper.int_neg(frac.__dict._num)
local q = fractions_helper.int_op(neg_n, frac.__dict._den, "//")
return fractions_helper.int_neg(q)
end
function fractions_helper.math_trunc(frac)
local n, d = frac.__dict._num, frac.__dict._den
if fractions_helper.int_sign(n) < 0 then
local pos_q = fractions_helper.int_op(fractions_helper.int_neg(n), d, "//")
return fractions_helper.int_neg(pos_q)
end
return fractions_helper.int_op(n, d, "//")
end
local function int_ln(val)
if type(val) == "number" then return math.log(val) end
local BigInt = require("Module:沙盒/a2569875/PythonScript/Runtime/Cmath").BigInt
local s = BigInt.to_string(1, val.limbs)
local k = #s - 1
local m = tonumber(s:sub(1, 1) .. "." .. s:sub(2, 17)) or 1.0
return math.log(m) + k * math.log(10)
end
function fractions_helper.math_log(frac, base)
local Runtime = require("Module:沙盒/a2569875/PythonScript/Runtime")
local n, d = frac.__dict._num, frac.__dict._den
if fractions_helper.int_sign(n) <= 0 then
Runtime.raise("ValueError", "math domain error")
end
local ln_val = int_ln(n) - int_ln(d)
if base ~= nil and not fractions_helper.is_none(base) then
local b_ln
if fractions_helper.is_fraction(base) then
b_ln = fractions_helper.math_log(base)
else
local bf = tonumber(tostring(base))
if not bf or bf <= 0 then Runtime.raise("ValueError", "math domain error") end
b_ln = math.log(bf)
end
return ln_val / b_ln
end
return ln_val
end
function fractions_helper.math_log10(frac)
return fractions_helper.math_log(frac) / math.log(10)
end
function fractions_helper.math_log2(frac)
return fractions_helper.math_log(frac) / math.log(2)
end
-- ==========================================
-- 5. 延遲初始化 Fraction 類別與所有魔術方法
-- ==========================================
function fractions_helper.ensure_init()
if fractions_helper.initialized then return end
fractions_helper.initialized = true
local PyClass = require("Module:沙盒/a2569875/PythonScript/Class")
local Runtime = require("Module:沙盒/a2569875/PythonScript/Runtime")
local B = Runtime.builtins
local C = fractions_helper.cache
local function to_nd_or_float(other)
if fractions_helper.is_fraction(other) then return "frac", other.__dict._num, other.__dict._den end
if fractions_helper.is_int(other) then
return "frac", (type(other) == "boolean" and (other and 1 or 0) or other), 1
end
if type(other) == "number" then return "float", other end
return nil
end
local frac_dict
frac_dict = {
__new__ = { __type = "staticmethod", __func = { __type = "builtin_method", __name = "__new__", __call = function(a, kw)
local cls = a[1]
local num_arg = (a[2] ~= nil) and a[2] or (kw and kw.numerator) or 0
local den_arg = (a[3] ~= nil) and a[3] or (kw and kw.denominator) or B.None
local n, d
if fractions_helper.is_none(den_arg) then
n, d = fractions_helper.coerce_single(num_arg)
else
local n1, d1
if fractions_helper.is_int(num_arg) then
n1, d1 = (type(num_arg) == "boolean" and (num_arg and 1 or 0) or num_arg), 1
elseif fractions_helper.is_fraction(num_arg) then
n1, d1 = num_arg.__dict._num, num_arg.__dict._den
else
Runtime.raise("TypeError", "both arguments should be Rational instances")
end
local n2, d2
if fractions_helper.is_int(den_arg) then
n2, d2 = (type(den_arg) == "boolean" and (den_arg and 1 or 0) or den_arg), 1
elseif fractions_helper.is_fraction(den_arg) then
n2, d2 = den_arg.__dict._num, den_arg.__dict._den
else
Runtime.raise("TypeError", "both arguments should be Rational instances")
end
if fractions_helper.int_zero(n2) then
Runtime.raise("ZeroDivisionError", "Fraction(" .. tostring(n1) .. ", 0)")
end
n = fractions_helper.int_op(n1, d2, "*")
d = fractions_helper.int_op(d1, n2, "*")
n, d = fractions_helper.normalize_nd(n, d)
end
local inst = PyClass.make_instance(cls)
inst.__dict._is_fraction = true
inst.__dict._num = n
inst.__dict._den = d
return inst
end } },
__init__ = { __type = "builtin_method", __name = "__init__", __call = function() return nil end },
from_float = { __type = "classmethod", __func = { __type = "builtin_method", __name = "from_float", __call = function(a)
local cls, f = a[1], a[2]
if not fractions_helper.is_int(f) and type(f) ~= "number" then
Runtime.raise("TypeError", "from_float() only takes floats or ints")
end
local n, d = fractions_helper.coerce_single(f)
local inst = fractions_helper.make_fraction(n, d)
inst.__class = cls
return inst
end } },
from_decimal = { __type = "classmethod", __func = { __type = "builtin_method", __name = "from_decimal", __call = function(a)
local cls, dec = a[1], a[2]
if not fractions_helper.is_decimal(dec) and not fractions_helper.is_int(dec) then
Runtime.raise("TypeError", "from_decimal() only takes Decimals or ints")
end
local n, d = fractions_helper.coerce_single(dec)
local inst = fractions_helper.make_fraction(n, d)
inst.__class = cls
return inst
end } },
-- 屬性與基礎方法
numerator = { __type = "property", fget = { __type = "builtin_method", __call = function(a) return a[1].__dict._num end } },
denominator = { __type = "property", fget = { __type = "builtin_method", __call = function(a) return a[1].__dict._den end } },
real = { __type = "property", fget = { __type = "builtin_method", __call = function(a) return a[1] end } },
imag = { __type = "property", fget = { __type = "builtin_method", __call = function() return 0 end } },
conjugate = { __type = "builtin_method", __call = function(a) return a[1] end },
as_integer_ratio = { __type = "builtin_method", __call = function(a)
return { __type = "tuple", elements = { a[1].__dict._num, a[1].__dict._den } }
end },
is_integer = { __type = "builtin_method", __call = function(a)
return fractions_helper.int_cmp(a[1].__dict._den, 1) == 0
end },
limit_denominator = { __type = "builtin_method", __call = function(a, kw)
local self = a[1]
local max_d = (a[2] ~= nil and a[2]) or (kw and kw.max_denominator) or 1000000
local n, d = fractions_helper.limit_denominator_raw(self.__dict._num, self.__dict._den, max_d)
return fractions_helper.make_fraction(n, d)
end },
-- 字串與格式化
__str__ = { __type = "builtin_method", __call = function(a)
local n, d = a[1].__dict._num, a[1].__dict._den
local ns = B.str.__call({n})
if fractions_helper.int_cmp(d, 1) == 0 then return ns end
return ns .. "/" .. B.str.__call({d})
end },
__repr__ = { __type = "builtin_method", __call = function(a)
local n, d = a[1].__dict._num, a[1].__dict._den
return "Fraction(" .. B.str.__call({n}) .. ", " .. B.str.__call({d}) .. ")"
end },
__format__ = { __type = "builtin_method", __call = function(a)
local self, spec = a[1], a[2] or ""
if spec == "" then return B.str.__call({self}) end
if spec:match("[eEfFgG%%]$") then
return B.format({ fractions_helper.to_float(self), spec })
end
return B.format({ B.str.__call({self}), spec })
end },
-- 型別轉換與捨入
__bool__ = { __type = "builtin_method", __call = function(a) return not fractions_helper.int_zero(a[1].__dict._num) end },
__float__ = { __type = "builtin_method", __call = function(a) return fractions_helper.to_float(a[1]) end },
__int__ = { __type = "builtin_method", __call = function(a) return fractions_helper.math_trunc(a[1]) end },
__trunc__ = { __type = "builtin_method", __call = function(a) return fractions_helper.math_trunc(a[1]) end },
__floor__ = { __type = "builtin_method", __call = function(a) return fractions_helper.math_floor(a[1]) end },
__ceil__ = { __type = "builtin_method", __call = function(a) return fractions_helper.math_ceil(a[1]) end },
__hash__ = { __type = "builtin_method", __call = function(a)
return B.hash({ fractions_helper.to_float(a[1]) })
end },
__round__ = { __type = "builtin_method", __call = function(a)
local self, ndigits = a[1], a[2]
local shift = 1
local has_nd = not fractions_helper.is_none(ndigits)
local n_digits = has_nd and tonumber(ndigits) or 0
local n, d = self.__dict._num, self.__dict._den
if n_digits > 0 then
shift = fractions_helper.pow10(n_digits)
n = fractions_helper.int_op(n, shift, "*")
elseif n_digits < 0 then
shift = fractions_helper.pow10(-n_digits)
d = fractions_helper.int_op(d, shift, "*")
end
local q = fractions_helper.int_op(n, d, "//")
local r = fractions_helper.int_op(n, d, "%")
local two_r = fractions_helper.int_op(r, 2, "*")
local cmp = fractions_helper.int_cmp(two_r, d)
if cmp > 0 or (cmp == 0 and not fractions_helper.int_zero(fractions_helper.int_op(q, 2, "%"))) then
q = fractions_helper.int_op(q, 1, "+")
end
if not has_nd then return q end
if n_digits >= 0 then return fractions_helper.make_fraction(q, shift)
else return fractions_helper.make_fraction(fractions_helper.int_op(q, shift, "*"), 1) end
end },
-- 一元與二元算術運算
__pos__ = { __type = "builtin_method", __call = function(a) return fractions_helper.make_fraction(a[1].__dict._num, a[1].__dict._den) end },
__neg__ = { __type = "builtin_method", __call = function(a)
return fractions_helper.make_fraction(fractions_helper.int_neg(a[1].__dict._num), a[1].__dict._den)
end },
__abs__ = { __type = "builtin_method", __call = function(a)
return fractions_helper.make_fraction(fractions_helper.int_abs(a[1].__dict._num), a[1].__dict._den)
end },
__add__ = { __type = "builtin_method", __call = function(a)
local self, other = a[1], a[2]
local kind, bn, bd = to_nd_or_float(other)
if kind == "frac" then
local an, ad = self.__dict._num, self.__dict._den
local num = fractions_helper.int_op(fractions_helper.int_op(an, bd, "*"), fractions_helper.int_op(bn, ad, "*"), "+")
local den = fractions_helper.int_op(ad, bd, "*")
return fractions_helper.make_fraction(num, den)
elseif kind == "float" then
return fractions_helper.to_float(self) + bn
end
return B.NotImplemented
end },
__radd__ = { __type = "builtin_method", __call = function(a)
return frac_dict.__add__.__call({ a[1], a[2] })
end },
__sub__ = { __type = "builtin_method", __call = function(a)
local self, other = a[1], a[2]
local kind, bn, bd = to_nd_or_float(other)
if kind == "frac" then
local an, ad = self.__dict._num, self.__dict._den
local num = fractions_helper.int_op(fractions_helper.int_op(an, bd, "*"), fractions_helper.int_op(bn, ad, "*"), "-")
local den = fractions_helper.int_op(ad, bd, "*")
return fractions_helper.make_fraction(num, den)
elseif kind == "float" then
return fractions_helper.to_float(self) - bn
end
return B.NotImplemented
end },
__rsub__ = { __type = "builtin_method", __call = function(a)
local self, left = a[1], a[2]
local kind, an, ad = to_nd_or_float(left)
if kind == "frac" then
local bn, bd = self.__dict._num, self.__dict._den
local num = fractions_helper.int_op(fractions_helper.int_op(an, bd, "*"), fractions_helper.int_op(bn, ad, "*"), "-")
local den = fractions_helper.int_op(ad, bd, "*")
return fractions_helper.make_fraction(num, den)
elseif kind == "float" then
return an - fractions_helper.to_float(self)
end
return B.NotImplemented
end },
__mul__ = { __type = "builtin_method", __call = function(a)
local self, other = a[1], a[2]
local kind, bn, bd = to_nd_or_float(other)
if kind == "frac" then
return fractions_helper.make_fraction(
fractions_helper.int_op(self.__dict._num, bn, "*"),
fractions_helper.int_op(self.__dict._den, bd, "*")
)
elseif kind == "float" then
return fractions_helper.to_float(self) * bn
end
return B.NotImplemented
end },
__rmul__ = { __type = "builtin_method", __call = function(a)
return frac_dict.__mul__.__call({ a[1], a[2] })
end },
__truediv__ = { __type = "builtin_method", __call = function(a)
local self, other = a[1], a[2]
local kind, bn, bd = to_nd_or_float(other)
if kind == "frac" then
if fractions_helper.int_zero(bn) then Runtime.raise("ZeroDivisionError", "Fraction division by zero") end
return fractions_helper.make_fraction(
fractions_helper.int_op(self.__dict._num, bd, "*"),
fractions_helper.int_op(self.__dict._den, bn, "*")
)
elseif kind == "float" then
if bn == 0.0 then Runtime.raise("ZeroDivisionError", "float division by zero") end
return fractions_helper.to_float(self) / bn
end
return B.NotImplemented
end },
__rtruediv__ = { __type = "builtin_method", __call = function(a)
local self, left = a[1], a[2]
local kind, an, ad = to_nd_or_float(left)
if kind == "frac" then
if fractions_helper.int_zero(self.__dict._num) then Runtime.raise("ZeroDivisionError", "Fraction division by zero") end
return fractions_helper.make_fraction(
fractions_helper.int_op(an, self.__dict._den, "*"),
fractions_helper.int_op(ad, self.__dict._num, "*")
)
elseif kind == "float" then
local sf = fractions_helper.to_float(self)
if sf == 0.0 then Runtime.raise("ZeroDivisionError", "float division by zero") end
return an / sf
end
return B.NotImplemented
end },
__floordiv__ = { __type = "builtin_method", __call = function(a)
local div_res = frac_dict.__truediv__.__call(a)
if div_res == B.NotImplemented then return B.NotImplemented end
if fractions_helper.is_fraction(div_res) then return fractions_helper.math_floor(div_res) end
return math.floor(div_res)
end },
__rfloordiv__ = { __type = "builtin_method", __call = function(a)
local div_res = frac_dict.__rtruediv__.__call(a)
if div_res == B.NotImplemented then return B.NotImplemented end
if fractions_helper.is_fraction(div_res) then return fractions_helper.math_floor(div_res) end
return math.floor(div_res)
end },
__mod__ = { __type = "builtin_method", __call = function(a)
local q = frac_dict.__floordiv__.__call(a)
if q == B.NotImplemented then return B.NotImplemented end
local prod = frac_dict.__mul__.__call({ a[1], q })
-- self - other * (self // other)
local step = frac_dict.__mul__.__call({ a[1], 1 })
if type(a[2]) == "number" and not fractions_helper.is_int(a[2]) then
return fractions_helper.to_float(a[1]) % a[2]
end
local _, bn, bd = to_nd_or_float(a[2])
local rhs = fractions_helper.make_fraction(fractions_helper.int_op(bn, q, "*"), bd)
return frac_dict.__sub__.__call({ step, rhs })
end },
__rmod__ = { __type = "builtin_method", __call = function(a)
local q = frac_dict.__rfloordiv__.__call(a)
if q == B.NotImplemented then return B.NotImplemented end
if type(a[2]) == "number" and not fractions_helper.is_int(a[2]) then
return a[2] % fractions_helper.to_float(a[1])
end
local prod = frac_dict.__mul__.__call({ a[1], q })
return frac_dict.__rsub__.__call({ prod, a[2] })
end },
__divmod__ = { __type = "builtin_method", __call = function(a)
local q = frac_dict.__floordiv__.__call(a)
if q == B.NotImplemented then return B.NotImplemented end
local r = frac_dict.__mod__.__call(a)
return { __type = "tuple", elements = { q, r } }
end },
__rdivmod__ = { __type = "builtin_method", __call = function(a)
local q = frac_dict.__rfloordiv__.__call(a)
if q == B.NotImplemented then return B.NotImplemented end
local r = frac_dict.__rmod__.__call(a)
return { __type = "tuple", elements = { q, r } }
end },
__pow__ = { __type = "builtin_method", __call = function(a)
local self, other = a[1], a[2]
local kind, bn, bd = to_nd_or_float(other)
if kind == "frac" and fractions_helper.int_cmp(bd, 1) == 0 then
local exp = bn
local n, d = self.__dict._num, self.__dict._den
if fractions_helper.int_sign(exp) >= 0 then
return fractions_helper.make_fraction(B.pow({n, exp}), B.pow({d, exp}))
else
if fractions_helper.int_zero(n) then Runtime.raise("ZeroDivisionError", "Fraction(0, 1) cannot be raised to a negative power") end
local pos_e = fractions_helper.int_neg(exp)
return fractions_helper.make_fraction(B.pow({d, pos_e}), B.pow({n, pos_e}))
end
elseif kind then
local exp_f = (kind == "frac") and (bn / bd) or bn
return fractions_helper.to_float(self) ^ exp_f
end
return B.NotImplemented
end },
__rpow__ = { __type = "builtin_method", __call = function(a)
local self, left = a[1], a[2]
if fractions_helper.int_cmp(self.__dict._den, 1) == 0 and fractions_helper.is_int(left) then
local exp = self.__dict._num
if fractions_helper.int_sign(exp) >= 0 then
return fractions_helper.make_fraction(B.pow({left, exp}), 1)
else
if fractions_helper.int_zero(left) then Runtime.raise("ZeroDivisionError", "0.0 cannot be raised to a negative power") end
return fractions_helper.make_fraction(1, B.pow({left, fractions_helper.int_neg(exp)}))
end
end
local lf = tonumber(tostring(left))
if lf then return lf ^ fractions_helper.to_float(self) end
return B.NotImplemented
end },
-- 比較運算 (支援與 int / BigInt / Fraction / Decimal / float 精確比較)
__eq__ = { __type = "builtin_method", __call = function(a)
local self, other = a[1], a[2]
local kind, bn, bd = to_nd_or_float(other)
if not kind and fractions_helper.is_decimal(other) then
local ok, dn, dd = pcall(fractions_helper.coerce_single, other)
if ok then kind, bn, bd = "frac", dn, dd else return false end
end
if kind == "frac" then
return fractions_helper.int_cmp(self.__dict._num, bn) == 0
and fractions_helper.int_cmp(self.__dict._den, bd) == 0
elseif kind == "float" then
if bn ~= bn then return false end
if bn == math.huge or bn == -math.huge then return false end
return fractions_helper.to_float(self) == bn
end
return B.NotImplemented
end },
__ne__ = { __type = "builtin_method", __call = function(a)
local eq = frac_dict.__eq__.__call(a)
if eq == B.NotImplemented then return B.NotImplemented end
return not eq
end }
}
local function make_cmp_method(op_fn)
return { __type = "builtin_method", __call = function(a)
local self, other = a[1], a[2]
local kind, bn, bd = to_nd_or_float(other)
if not kind and fractions_helper.is_decimal(other) then
local ok, dn, dd = pcall(fractions_helper.coerce_single, other)
if ok then kind, bn, bd = "frac", dn, dd end
end
if kind == "frac" then
local lhs = fractions_helper.int_op(self.__dict._num, bd, "*")
local rhs = fractions_helper.int_op(bn, self.__dict._den, "*")
return op_fn(fractions_helper.int_cmp(lhs, rhs), 0)
elseif kind == "float" then
if bn ~= bn then return false end
return op_fn(fractions_helper.to_float(self), bn)
end
return B.NotImplemented
end }
end
frac_dict.__lt__ = make_cmp_method(function(x, y) return x < y end)
frac_dict.__le__ = make_cmp_method(function(x, y) return x <= y end)
frac_dict.__gt__ = make_cmp_method(function(x, y) return x > y end)
frac_dict.__ge__ = make_cmp_method(function(x, y) return x >= y end)
frac_dict.__copy__ = frac_dict.__pos__
frac_dict.__deepcopy__ = frac_dict.__pos__
C.Fraction = PyClass.make_class("Fraction", {}, frac_dict)
C.Fraction.__dict["__module__"] = "fractions"
C.gcd = { __type = "builtin_method", __name = "gcd", __call = function(a)
return fractions_helper.int_gcd(a[1] or 0, a[2] or 0)
end }
end
-- ==========================================
-- 6. 模組匯出工廠
-- ==========================================
function fractions_helper.get_module()
local PyClass = require("Module:沙盒/a2569875/PythonScript/Class")
local Runtime = require("Module:沙盒/a2569875/PythonScript/Runtime")
local mod_dict = {
__getattr__ = {
__type = "builtin_method",
__call = function(args)
local self, attr = args[1], args[2]
fractions_helper.ensure_init()
local val = fractions_helper.cache[attr]
if val ~= nil then
self.__dict[attr] = val
return val
end
Runtime.raise("AttributeError", "module 'fractions' has no attribute '" .. tostring(attr) .. "'")
end
}
}
local mod = PyClass.make_instance(PyClass.make_class("module", {}, mod_dict))
mod.__dict["__name__"] = "fractions"
mod.__dict["__all__"] = { __type = "list", elements = { "Fraction", "gcd" } }
return mod
end
return fractions_helper
end
-- ==========================================
-- 3. graphlib 圖論演算法
-- ==========================================
function StdAlgorithms.graphlib()
local graphlib_helper = {
initialized = false,
cache = {}
}
function graphlib_helper.ensure_init()
if graphlib_helper.initialized then return end
graphlib_helper.initialized = true
local PyClass = require("Module:沙盒/a2569875/PythonScript/Class")
local Runtime = require("Module:沙盒/a2569875/PythonScript/Runtime")
local B = Runtime.builtins
local EvalUtils = require("Module:沙盒/a2569875/PythonScript/Evaluator/Utils")
local Evaluator = require("Module:沙盒/a2569875/PythonScript/Evaluator")
-- 1. CycleError 例外類別
local CycleError = PyClass.make_class("CycleError", { B.ValueError }, {})
CycleError.__dict["__module__"] = "graphlib"
graphlib_helper.cache.CycleError = CycleError
-- 2. TopologicalSorter 內部輔助函式 (節點映射)
local function get_node_id(d, node)
for id, n in ipairs(d._id2node) do
if EvalUtils.py_eq(n, node) then return id end
end
local new_id = #d._id2node + 1
d._id2node[new_id] = node
d._preds[new_id] = {}
return new_id
end
local function get_existing_node_id(d, node)
for id, n in ipairs(d._id2node) do
if EvalUtils.py_eq(n, node) then return id end
end
Runtime.raise("ValueError", "node was not added using add()")
end
-- 3. TopologicalSorter 核心類別字典
local ts_dict = {
__init__ = { __type = "builtin_method", __call = function(a, kw)
local self = a[1]
local d = self.__dict
d._id2node = {}
d._preds = {}
d._succs = {}
d._in_degree = {}
d._ready_nodes = {}
d._passed_out = {}
d._finished = {}
d._n_passed_out = 0
d._n_finished = 0
d._prepared = false
local graph = (a[2] ~= nil) and a[2] or (kw and kw.graph) or B.None
if graph ~= B.None then
local items_fn = PyClass.get_attr(graph, "items")
local iter_state = EvalUtils.make_iter_state(Evaluator.invoke(items_fn, {}, {}, graph))
while true do
local has_next, pair = EvalUtils.get_next_item(iter_state)
if not has_next then break end
local node = pair.elements[1]
local preds = pair.elements[2]
local p_state = EvalUtils.make_iter_state(preds)
local add_args = {self, node}
while true do
local hn, p = EvalUtils.get_next_item(p_state)
if not hn then break end
table.insert(add_args, p)
end
-- 利用 self.add 方法寫入圖
self.__class.__dict.add.__call(add_args)
end
end
return nil
end },
add = { __type = "builtin_method", __call = function(a)
local self, node = a[1], a[2]
local d = self.__dict
if d._prepared then Runtime.raise("ValueError", "Nodes cannot be added after a call to prepare()") end
local node_id = get_node_id(d, node)
for i = 3, #a do
local pred_id = get_node_id(d, a[i])
table.insert(d._preds[node_id], pred_id)
end
return B.None
end },
prepare = { __type = "builtin_method", __call = function(a)
local self = a[1]
local d = self.__dict
if d._prepared then Runtime.raise("ValueError", "cannot prepare() more than once") end
d._prepared = true
-- 建立後繼者字典 (successors) 與初始入度
for id = 1, #d._id2node do d._succs[id] = {} end
for node_id, preds in pairs(d._preds) do
local unique_preds = {}
local seen = {}
for _, pred_id in ipairs(preds) do
if not seen[pred_id] then
seen[pred_id] = true
table.insert(unique_preds, pred_id)
table.insert(d._succs[pred_id], node_id)
end
end
d._preds[node_id] = unique_preds
d._in_degree[node_id] = #unique_preds
end
-- DFS 演算法：偵測循環依賴 (Cycle Detection)
local state = {}
local path = {}
local function dfs(u)
state[u] = 1
table.insert(path, u)
for _, v in ipairs(d._succs[u]) do
if state[v] == 1 then
local cycle_nodes = {}
local in_cycle = false
for _, pid in ipairs(path) do
if pid == v then in_cycle = true end
if in_cycle then
table.insert(cycle_nodes, d._id2node[pid])
end
end
table.insert(cycle_nodes, d._id2node[v])
return cycle_nodes
elseif not state[v] then
local c = dfs(v)
if c then return c end
end
end
state[u] = 2
table.remove(path)
return nil
end
for id = 1, #d._id2node do
if not state[id] then
local cycle = dfs(id)
if cycle then
local tup = { __type = "tuple", elements = cycle }
local exc = PyClass.make_instance(CycleError)
exc.__dict.args = { __type = "tuple", elements = { "nodes are in a cycle", tup } }
exc.__dict.msg = "nodes are in a cycle"
Runtime.raise(exc)
end
end
end
-- 蒐集初始狀態下就緒 (無依賴) 的節點
for id = 1, #d._id2node do
if d._in_degree[id] == 0 then
table.insert(d._ready_nodes, id)
end
end
return B.None
end },
is_active = { __type = "builtin_method", __call = function(a)
local d = a[1].__dict
if not d._prepared then Runtime.raise("ValueError", "prepare() must be called first") end
-- 只要還有就緒的節點，或是有已經釋出但尚未標記為 done 的節點，代表進度仍能推進
return (d._n_passed_out > d._n_finished) or (#d._ready_nodes > 0)
end },
done = { __type = "builtin_method", __call = function(a)
local self = a[1]
local d = self.__dict
if not d._prepared then Runtime.raise("ValueError", "prepare() must be called first") end
for i = 2, #a do
local node = a[i]
local id = get_existing_node_id(d, node)
if not d._passed_out[id] then
Runtime.raise("ValueError", "node was not passed out (not ready yet)")
end
if d._finished[id] then
Runtime.raise("ValueError", "node was already marked done")
end
d._finished[id] = true
d._n_finished = d._n_finished + 1
for _, succ_id in ipairs(d._succs[id]) do
d._in_degree[succ_id] = d._in_degree[succ_id] - 1
if d._in_degree[succ_id] == 0 then
table.insert(d._ready_nodes, succ_id)
end
end
end
return B.None
end },
get_ready = { __type = "builtin_method", __call = function(a)
local self = a[1]
local d = self.__dict
if not d._prepared then Runtime.raise("ValueError", "prepare() must be called first") end
local res = {}
for _, id in ipairs(d._ready_nodes) do
table.insert(res, d._id2node[id])
d._passed_out[id] = true
d._n_passed_out = d._n_passed_out + 1
end
d._ready_nodes = {}
return { __type = "tuple", elements = res }
end },
static_order = { __type = "builtin_method", __call = function(a)
local self = a[1]
local d = self.__dict
if not d._prepared then
self.__class.__dict.prepare.__call({self})
end
local out = {}
while self.__class.__dict.is_active.__call({self}) do
local ready = self.__class.__dict.get_ready.__call({self})
if #ready.elements == 0 then
-- 靜態解析下如果發生中斷，即代表非預期狀態 (循環已在 prepare 階段被攔截)
break
end
local done_args = {self}
for _, node in ipairs(ready.elements) do
table.insert(out, node)
table.insert(done_args, node)
end
self.__class.__dict.done.__call(done_args)
end
return B.iter({ { __type = "list", elements = out } })
end }
}
local TopologicalSorter = PyClass.make_class("TopologicalSorter", {}, ts_dict)
TopologicalSorter.__dict["__module__"] = "graphlib"
graphlib_helper.cache.TopologicalSorter = TopologicalSorter
end
function graphlib_helper.get_module()
graphlib_helper.ensure_init()
local PyClass = require("Module:沙盒/a2569875/PythonScript/Class")
local Runtime = require("Module:沙盒/a2569875/PythonScript/Runtime")
local mod_dict = {
__getattr__ = {
__type = "builtin_method",
__call = function(args)
local self, attr = args[1], args[2]
local val = graphlib_helper.cache[attr]
if val ~= nil then
self.__dict[attr] = val
return val
end
Runtime.raise("AttributeError", "module 'graphlib' has no attribute '" .. tostring(attr) .. "'")
end
}
}
local mod = PyClass.make_instance(PyClass.make_class("module", {}, mod_dict))
mod.__dict["__name__"] = "graphlib"
mod.__dict["__all__"] = {
__type = "list",
elements = { "TopologicalSorter", "CycleError" }
}
return mod
end
return graphlib_helper
end
-- ==========================================
-- 4. hashlib 雜湊演算法
-- ==========================================
function StdAlgorithms.hash()
local Hashlib = {}
local PyClass = require("Module:沙盒/a2569875/PythonScript/Class")
local Runtime = require("Module:沙盒/a2569875/PythonScript/Runtime")
local RUtils = require("Module:沙盒/a2569875/PythonScript/Runtime/Utils")
local bit32 = require("bit32")
local B = Runtime.builtins
-- 維基百科 mw.hash 支援的演算法映射
local AVAILABLE_ALGORITHMS = {
["md5"] = true, ["sha1"] = true, ["sha224"] = true,
["sha256"] = true, ["sha384"] = true, ["sha512"] = true
}
local function fn(name, func) return { __type = "builtin_method", __name = name, __call = func } end
local function hex_to_bytes(hex)
return (hex:gsub("%x%x", function(h) return string.char(tonumber(h, 16)) end))
end
local function extract_bytes(obj)
if type(obj) == "table" and (obj.__type == "bytes" or obj.__type == "bytearray" or obj.__type == "memoryview") then
if obj.__type == "memoryview" and obj._released then Runtime.raise("ValueError", "operation forbidden on released memoryview object") end
return obj._data
end
if type(obj) == "string" then return obj end
Runtime.raise("TypeError", "a bytes-like object is required, not '" .. RUtils.get_type_str(obj) .. "'")
end
-- ==========================================
-- 1. 雜湊物件 (Hash Object) 類別實作
-- ==========================================
local hash_dict = {
__module__ = "hashlib",
__init__ = fn("__init__", function(a, kw)
local self, name = a[1], a[2]
self.__dict._name = tostring(name):lower()
if not AVAILABLE_ALGORITHMS[self.__dict._name] then
Runtime.raise("ValueError", "unsupported hash type " .. self.__dict._name)
end
self.__dict._buffer = {}
local data = (a[3] ~= nil) and a[3] or (kw and kw.data)
if data then
table.insert(self.__dict._buffer, extract_bytes(data))
end
return nil
end),
update = fn("update", function(a)
local self, data = a[1], a[2]
table.insert(self.__dict._buffer, extract_bytes(data))
return B.None
end),
digest = fn("digest", function(a)
local self = a[1]
local raw_data = table.concat(self.__dict._buffer)
local hex_str = mw.hash.hashValue(self.__dict._name, raw_data)
return { __type = "bytes", _data = hex_to_bytes(hex_str) }
end),
hexdigest = fn("hexdigest", function(a)
local self = a[1]
local raw_data = table.concat(self.__dict._buffer)
return mw.hash.hashValue(self.__dict._name, raw_data)
end),
copy = fn("copy", function(a)
local self = a[1]
local new_inst = PyClass.make_instance(self.__class)
new_inst.__dict._name = self.__dict._name
new_inst.__dict._buffer = {}
for _, v in ipairs(self.__dict._buffer) do table.insert(new_inst.__dict._buffer, v) end
return new_inst
end),
name = {
__type = "property",
fget = fn("name", function(a) return a[1].__dict._name end)
},
digest_size = {
__type = "property",
fget = fn("digest_size", function(a)
local sizes = { md5 = 16, sha1 = 20, sha224 = 28, sha256 = 32, sha384 = 48, sha512 = 64 }
return sizes[a[1].__dict._name] or 32
end)
},
block_size = {
__type = "property",
fget = fn("block_size", function(a)
local sizes = { md5 = 64, sha1 = 64, sha224 = 64, sha256 = 64, sha384 = 128, sha512 = 128 }
return sizes[a[1].__dict._name] or 64
end)
}
}
local HashClass = PyClass.make_class("HASH", { B.object }, hash_dict)
local function make_hash_wrapper(algo_name)
return fn(algo_name, function(a)
local data = a[1]
local inst = PyClass.make_instance(HashClass)
inst.__dict._name = algo_name
inst.__dict._buffer = {}
if data ~= nil then table.insert(inst.__dict._buffer, extract_bytes(data)) end
return inst
end)
end
-- ==========================================
-- 2. PBKDF2 HMAC 純 Lua 輕量級實作
-- ==========================================
local function bxor_bytes(b1, b2)
local res = {}
for i = 1, #b1 do res[i] = string.char(bit32.bxor(string.byte(b1, i), string.byte(b2, i))) end
return table.concat(res)
end
local function native_hmac(algo, key, msg)
local block_size = (algo == "sha384" or algo == "sha512") and 128 or 64
if #key > block_size then key = hex_to_bytes(mw.hash.hashValue(algo, key)) end
if #key < block_size then key = key .. string.rep("\0", block_size - #key) end
local opad = bxor_bytes(key, string.rep(string.char(0x5c), block_size))
local ipad = bxor_bytes(key, string.rep(string.char(0x36), block_size))
local inner = hex_to_bytes(mw.hash.hashValue(algo, ipad .. msg))
return hex_to_bytes(mw.hash.hashValue(algo, opad .. inner))
end
local function pbkdf2_hmac(a, kw)
local hash_name = tostring(a[1] or (kw and kw.hash_name)):lower()
local password = extract_bytes(a[2] or (kw and kw.password))
local salt = extract_bytes(a[3] or (kw and kw.salt))
local iterations = tonumber(RUtils.unwrap_num(a[4] or (kw and kw.iterations)))
local dklen = a[5] or (kw and kw.dklen)
if dklen == nil or dklen == B.None then
local sizes = { md5=16, sha1=20, sha224=28, sha256=32, sha384=48, sha512=64 }
dklen = sizes[hash_name] or 32
else
dklen = tonumber(RUtils.unwrap_num(dklen))
end
if not AVAILABLE_ALGORITHMS[hash_name] then Runtime.raise("ValueError", "unsupported hash type") end
if type(iterations) ~= "number" or iterations < 1 then Runtime.raise("ValueError", "iteration value must be >= 1") end
local out = {}
local blocks_needed = math.ceil(dklen / (hash_name == "sha384" and 48 or (hash_name == "sha512" and 64 or (hash_name == "sha224" and 28 or (hash_name == "sha1" and 20 or (hash_name == "md5" and 16 or 32))))))
local hash_len = (hash_name == "sha384" and 48 or (hash_name == "sha512" and 64 or (hash_name == "sha224" and 28 or (hash_name == "sha1" and 20 or (hash_name == "md5" and 16 or 32)))))
for i = 1, blocks_needed do
local block_idx = string.char(bit32.band(bit32.rshift(i, 24), 0xFF), bit32.band(bit32.rshift(i, 16), 0xFF), bit32.band(bit32.rshift(i, 8), 0xFF), bit32.band(i, 0xFF))
local U = native_hmac(hash_name, password, salt .. block_idx)
local T = U
for j = 2, iterations do
U = native_hmac(hash_name, password, U)
T = bxor_bytes(T, U)
end
table.insert(out, T)
end
local final_bytes = string.sub(table.concat(out), 1, dklen)
return { __type = "bytes", _data = final_bytes }
end
-- ==========================================
-- 3. 模組註冊與匯出
-- ==========================================
function Hashlib.get_module()
local mod = PyClass.make_instance(PyClass.make_class("module", {}, {}))
local d = mod.__dict
d["__name__"] = "hashlib"
-- 註冊新建立介面與建構器
d.new = fn("new", function(a, kw)
local inst = PyClass.make_instance(HashClass)
HashClass.__dict.__init__.__call({inst, unpack(a)}, kw)
return inst
end)
d.md5 = make_hash_wrapper("md5")
d.sha1 = make_hash_wrapper("sha1")
d.sha224 = make_hash_wrapper("sha224")
d.sha256 = make_hash_wrapper("sha256")
d.sha384 = make_hash_wrapper("sha384")
d.sha512 = make_hash_wrapper("sha512")
d.pbkdf2_hmac = fn("pbkdf2_hmac", pbkdf2_hmac)
-- 註冊清單 (algorithms_guaranteed / algorithms_available)
local algo_list = { "md5", "sha1", "sha224", "sha256", "sha384", "sha512" }
local algo_set = B.set.__call({})
for _, name in ipairs(algo_list) do
table.insert(algo_set.elements, name)
end
d.algorithms_guaranteed = algo_set
d.algorithms_available = algo_set
return mod
end
return Hashlib
end
return StdAlgorithms
