PWAD   T  --- FlowerRNG 2.0 by tertu
-- To the extent possible, I place this in the public domain worldwide.

-- Indebted to the work of M. E. O'Neill who wrote the blog posts that made me
-- aware of PractRand and of the ranged RNG techniques used in this engine and
-- Chris Doty-Humphry who developed this random-number generation technique,
-- named SFC32.
-- This is conceptually similar to SeedRng but reworked in a lot of ways.
-- Hence the name.

local sim_states = {}
local sim_state_counter = 1
local hud_states = {}
--This will cause the garbage collector to automatically delete HUD states
--that go out of scope. Don't rely on this though.
setmetatable(hud_states, {__mode='k'})
local unpack = unpack

addHook('NetVars', function(sync)
	sim_states = sync(sim_states)
	sim_state_counter = sync(sim_state_counter)
end)

-- This whole thing is based on the SFC32 RNG.
--sfc32 is characterized by 3 parameters.
--this is the source of the magic numbers 9, 3, and 21.
--(11 is just 32-21 which is needed for a 32 bit rotation)
local function generate_internal(real_state)
	local a, b, c, counter = unpack(real_state)
	local result = a + b + counter

	real_state[1] = b ^^ (b >> 9)
	real_state[2] = c + (c << 3)
	real_state[3] = ((c << 21) | (c >> 11)) + result
	real_state[4] = counter + 1

	return result
end

local function generate_many_internal(real_state, count)
	local a, b, c, counter = unpack(real_state)
	local output = {}

	for i=1,count do
		local result = a + b + counter
		counter = counter + 1
		a = b ^^ (b >> 9)
		b = c + (c << 3)
		c = ((c << 21) | (c >> 11)) + result
		output[i] = result
	end

	real_state[1] = a
	real_state[2] = b
	real_state[3] = c
	real_state[4] = counter
	return output
end

--This method was apparently originally developed at Apple. It's not the
--fastest method for generating a random number in a range in an unbiased way,
--but in SRB2 Lua, where there is no unsigned integer multiplication, it
--probably is.
local function generate_bounded_internal(real_state, range)
	if range == 0 or range == 1 then
		return 0
	end

	range = $ - 1

	--stolen from wikipedia (the apple method is designed around the assumption
	--that clz is something your language can just Do.)
	local remaining_range_bits = range | 1
	local leading_zeroes = 0
	if not (remaining_range_bits & 0xFFFF0000) then
		leading_zeroes = $ + 16
		remaining_range_bits = $ << 16
	end
	if not (remaining_range_bits & 0xFF000000) then
		leading_zeroes = $ + 8
		remaining_range_bits = $ << 8
	end
	if not (remaining_range_bits & 0xF0000000) then
		leading_zeroes = $ + 4
		remaining_range_bits = $ << 4
	end
	if not (remaining_range_bits & 0xC0000000) then
		leading_zeroes = $ + 2
		remaining_range_bits = $ << 2
	end
	if not (remaining_range_bits & 0x80000000) then
		leading_zeroes = $ + 1
	end

	local mask = 0xFFFFFFFF >> leading_zeroes
	local range_high_bit = range < 0

	local result
	local result_is_valid

	local a, b, c, counter = unpack(real_state)

	repeat
		--the generator but inlined.
		result = a + b + counter
		counter = counter + 1
		a = b ^^ (b >> 9)
		b = c + (c << 3)
		c = ((c << 21) | (c >> 11)) + result
		result = $ & mask

		--result_is_valid is true if the unsigned value of result is less than
		--or equal to the unsigned value of range. There are no unsigned
		--comparison functions, so it has to be computed indirectly.
		local result_high_bit = result < 0
		if range_high_bit ~= result_high_bit then
			-- if the high bits are different and the range high bit is set,
			-- the range must be greater than the result, and vice versa
			result_is_valid = range_high_bit
		else
			-- mask out the positive portion of the values and then compare them
			local value_mask = 0x7FFFFFFF
			result_is_valid = (result & value_mask) <= (range & value_mask)
		end
	until result_is_valid

	real_state[1] = a
	real_state[2] = b
	real_state[3] = c
	real_state[4] = counter
	return result
end

local function create_state_internal(seed_a, seed_b)
	--seed_a is expected to be provided by the caller
	--seed_b is optional

	local output = {}
	output[1] = 0
	output[2] = seed_b or 0xDEAD5EED
	output[3] = seed_a
	output[4] = 1

	-- State mixing
	generate_many_internal(output, 16)

	return output
end


--Note that this will wrap around if maximum is less than minimum.
local function generate_between_internal(real_state, minimum, maximum)
	local difference = maximum - minimum
	if difference == 0xFFFFFFFF then
		return generate_internal(real_state)
	end
	return generate_bounded_internal(real_state, difference+1) + minimum
end

--Shuffles an array in place using the Knuth shuffle.
--Note that if that array contains more than ~32 items, it may be impossible for
--every possible order of that array to happen. This probably is not a big deal
--but it's kinda interesting imo.
local function shuffle_internal(real_state, array)
	local array_size = #array
	if array_size > 1 then
		for item1=array_size, 2, -1 do
			local item2 = 1+generate_bounded_internal(real_state,item1-1)
			array[item1], array[item2] = $2, $1
		end
	end
end

-- Generates a fixed-point number approximately normally distributed around 0.
-- @param real_state a FlowerRNG state table
-- @param degree The number of deviates to consume, giving accuracy and range
-- @return a fixed-point number between +/-(FRACUNIT-1)*degree.
local function generate_normal_internal(real_state, degree)
	degree = ($ and $ > 6) and $ or 6
	local deviates = generate_many_internal(real_state, degree)
	local final_sample = 0
	local mask_and_limit = 65535

	for i=1,degree do
		local deviate = deviates[i]
		final_sample = final_sample + (deviate & mask_and_limit) + (deviate >> 16)
	end

	return final_sample - (degree*mask_and_limit)
end

-- Throws an error if in the HUD or not in the HUD depending on hud_mode
local function hud_check(hud_mode, err_level)
	-- This doesn't care about this function's result, but it will fail if
	-- NOHUD functions can't be called at this time. Because that's the criteria
	-- used to determine when it's okay to call Hud or Sim functions, this is
	-- useful.
	-- Earlier I used P_IsFlagAtBase for this, but I discovered that searches
	-- every mobj every time it is called. S_IdPlaying only searches every sound
	-- channel, which is usually 32, and what it does with them is simpler.
	local in_hud = not pcall(S_IdPlaying, 0)

	if in_hud ~= hud_mode then
		local message = hud_mode
			and "FlowerRNG: Sim functions cannot be used in HUD hooks."
			or "FlowerRNG: HUD functions cannot be used outside HUD hooks."
		error(message, err_level+1)
	end
end

local function token_to_state(token, hud_mode, err_level)
	hud_check(hud_mode, err_level + 1)

	local state_table = hud_mode and hud_states or sim_states
	local state = state_table[token]
	if not state then
		local message = hud_mode
			and "FlowerRNG: invalid HUD state: "
			or "FlowerRNG: invalid Sim state: "
		error(message .. tostring(token), err_level+1)
	end

	return state
end

local function user_int32_array(token, hud_mode, count, err_level)
	local state = token_to_state(token, hud_mode, err_level+1)

	if type(count) ~= 'number' then
		error("FlowerRNG: count must be a number", err_level+1)
	elseif count < 1 then
		error("FlowerRNG: count must be 1 or greater", err_level+1)
	else
		return generate_many_internal(state, count)
	end
end

local function user_between(token, hud_mode, minimum, maximum, wraparound, err_level)
	local state = token_to_state(token, hud_mode, err_level+1)
	if type(minimum) ~= 'number' or type(maximum) ~= 'number' then
		error("FlowerRNG: minimum and maximum must both be numbers", err_level+1)
	elseif maximum == minimum then
		error("FlowerRNG: a range of 0 is invalid", err_level+1)
	elseif maximum < minimum and not wraparound then
		error("FlowerRNG: wraparound is required if maximum < minimum", err_level+1)
	else
		return generate_between_internal(state, minimum, maximum)
	end
end

local function user_limit(token, hud_mode, range, err_level)
	local state = token_to_state(token, hud_mode, err_level+1)
	if type(range) ~= 'number' then
		error("FlowerRNG: limit must be a number", err_level+1)
	end

	if range < 0 then
		return generate_between_internal(state, range, 0)
	else
		return generate_bounded_internal(state, range+1)
	end
end

local function user_key(token, hud_mode, range, err_level)
	local state = token_to_state(token, hud_mode, err_level+1)
	if type(range) ~= 'number' then
		error("FlowerRNG: range must be a number", err_level+1)
	end
	return generate_bounded_internal(state, range)
end

local function user_normal(token, hud_mode, iterations, err_level)
	local state = token_to_state(token, hud_mode, err_level+1)
	local iterations_type = type(iterations)
	if iterations_type ~= 'number' and iterations_type ~= 'nil' then
		error("FlowerRNG: iterations must be a number or nil", err_level+1)
	end
	return generate_normal_internal(state, range)
end

local function user_shuffle(token, hud_mode, shuffle_table, err_level)
	local state = token_to_state(token, hud_mode, err_level+1)
	if type(shuffle_table) ~= 'table' then
		error("FlowerRNG: shuffle_table must be a table", err_level+1)
	end
	shuffle_internal(state, shuffle_table)
end

local function user_create(hud_mode, seed_a, seed_b, err_level)
	hud_check(hud_mode, err_level + 1)
	if type(seed_a) ~= 'number' or (seed_b ~= nil and type(seed_b) ~= 'number') then
		error("FlowerRNG: seeds must be numbers", err_level+1)
	end

	local token
	local state = create_state_internal(seed_a, seed_b)
	if hud_mode then
		token = {}
		hud_states[token] = state
	else
		token = sim_state_counter
		sim_state_counter = $ + 1
		sim_states[token] = state
	end

	return token
end

local function user_destroy(hud_mode, token, err_level)
	local state = token_to_state(token, hud_mode, err_level+1)

	if hud_mode then
		if hud_states[token] then
			hud_states[token] = nil
		end
	else
		if sim_states[token] then
			sim_states[token] = nil
		end
	end

end

local FRNG = {}

--- Create a new HUD FlowerRNG state.
-- @return A token that can be used to represent that state.
function FRNG.Hud_Create(a, b) return user_create(true, a, b, 1) end
function FRNG.Hud_Destroy(token) return user_destroy(true, token, 1) end

--- Get a random number between 0 and FRACUNIT-1.
-- This function is identical to SRB2's RandomFixed.
-- @param token A token representing a FlowerRNG HUD state
-- @return a fixed-point number as stated
-- @raise If not called from a HUD hook or called with an invalid or Sim token.
-- @see FRNG.Hud_Create
function FRNG.Hud_GetFixed(token)
	return generate_internal(token_to_state(token, true, 2)) & 0xFFFF
end

--- Get a random number between 0 and 255.
-- This function is identical to SRB2's RandomByte.
-- @param token A token representing a FlowerRNG HUD state
-- @return a number as stated
-- @raise If not called from a HUD hook or called with an invalid or Sim token.
-- @see FRNG.Hud_Create
function FRNG.Hud_GetByte(token)
	return generate_internal(token_to_state(token, true, 2)) & 0xFF
end

--- Get a random number between -128 and 127.
-- This function is identical to SRB2's RandomSigned.
-- @param token A token representing a FlowerRNG HUD state
-- @return a number as stated
-- @raise If not called from a HUD hook or called with an invalid or Sim token.
-- @see FRNG.Hud_Create
function FRNG.Hud_GetSigned(token)
	return (generate_internal(token_to_state(token, true, 2)) & 0xFF) - 128
end

--- Get a random number between INT32_MIN and INT32_MAX.
-- @param token A token representing a FlowerRNG HUD state
-- @return a number as stated
-- @raise If not called from a HUD hook or called with an invalid or Sim token.
-- @see FRNG.Hud_Create
function FRNG.Hud_GetInt32(token)
	return generate_internal(token_to_state(token, true, 2))
end

--- Get an array of random numbers between INT32_MIN and INT32_MAX.
-- @param token A token representing a FlowerRNG HUD state
-- @param count The number of random numbers needed.
-- @return an array count of random Int32s
-- @raise If not called from a HUD hook or called with an invalid or Sim token.
-- @raise If count is not a number or is less than 0.
-- @see FRNG.Hud_Create, FRNG.Hud_GetInt32
function FRNG.Hud_GetInt32Array(token, count)
	return user_int32_array(token, true, count, 1)
end

--- Get a random number between 0 and range-1.
-- This function is not exactly identical to the hud RandomKey function. For one
-- thing numbers from 0 to INT32_MAX will work as you expect, but range is
-- treated as unsigned, so the numbers generated will wrap around past
-- INT32_MAX.
-- @param token A token representing a FlowerRNG HUD state
-- @param range The maximum value to return+1.
-- @return a number as stated
-- @raise If not called from a HUD hook or called with an invalid or Sim token.
-- @raise If range is 0 or not a number.
-- @see FRNG.Hud_Create, FRNG.Hud_GetZeroToLimit
function FRNG.Hud_GetKey(token, range)
	return user_key(token, true, range, 1)
end

--- Get a random number between 0 and limit, inclusive.
-- The number is treated as signed.
-- @param token A token representing a FlowerRNG HUD state
-- @param range The maximum, or if negative minimum, value to return.
-- @return a number as stated
-- @raise If not called from a HUD hook or called with an invalid or Sim token.
-- @raise If limit is 0 or not a number.
-- @see FRNG.Hud_Create, FRNG.Hud_GetKey
function FRNG.Hud_GetZeroToLimit(token, limit)
	return user_limit(token, true, limit, 1)
end

--- Get a random number between minimum and maximum, inclusive.
-- If maximum is less than minimum, wraparound must be set to true, and the
-- results will exclude the numbers between minimum and maximum treated as
-- unsigned integers. (This behavior is disabled by default because it's weird.)
-- @param token A token representing a FlowerRNG HUD state
-- @param minimum The minimum value to return.
-- @param maximum The maximum value to return.
-- @param wraparound Whether to allow wraparound. Defaults to false.
-- @raise If not called from a HUD hook or called with an invalid or Sim token.
-- @raise If minimum or maximum is not a number.
-- @raise If maximum is less than minimum and wraparound is false or nil.
function FRNG.Hud_GetRange(token, minimum, maximum, wraparound)
	return user_between(token, true, minimum, maximum, wraparound, 2)
end

--- Get an approximately normally distributed fixed point number.
-- The higher the degree, the better the approximation of a normally distributed
-- number and the further from 0 the upper and lower limit of this number are.
-- @param token A token representing a FlowerRNG HUD state.
-- @param iterations The number of iterations to run. Optional, minimum is 6.
-- @raise If not called from a HUD hook or called with an invalid or Sim token.
-- @see FRNG.Hud_Create
function FRNG.Hud_GetApproxNormal(token, iterations)
	return user_normal(token, true, iterations, 1)
end

--- Shuffles a table in place.
-- Only the array part of the table will be shuffled.
-- @param token A token representing a FlowerRNG HUD state
-- @param shuffle_table A table to shuffle.
-- @return nothing
-- @raise If not called from a HUD hook or called with an invalid or Sim token.
-- @raise If shuffle_table is not a table.
function FRNG.Hud_Shuffle(token, shuffle_table)
	return user_shuffle(token, true, shuffle_table, 1)
end

--- Create a new Sim FlowerRNG state.
-- @return A token that can be used to represent that state.
function FRNG.Sim_Create(a, b) return user_create(false, a, b, 1) end
function FRNG.Sim_Destroy(token) return user_destroy(false, token, 1) end

--- Get a random number between 0 and FRACUNIT-1.
-- This function is identical to SRB2's RandomFixed.
-- @param token A token representing a FlowerRNG Sim state
-- @return a fixed-point number as stated
-- @raise If not called from a Sim hook or called with an invalid or HUD token.
-- @see FRNG.Sim_Create
function FRNG.Sim_GetFixed(token)
	return generate_internal(token_to_state(token, false, 2)) & 0xFFFF
end

--- Get a random number between 0 and 255.
-- This function is identical to SRB2's RandomByte.
-- @param token A token representing a FlowerRNG Sim state
-- @return a number as stated
-- @raise If called from a HUD hook or called with an invalid or HUD token.
-- @see FRNG.Sim_Create
function FRNG.Sim_GetByte(token)
	return generate_internal(token_to_state(token, false, 2)) & 0xFF
end

--- Get a random number between -128 and 127.
-- This function is identical to SRB2's RandomSigned.
-- @param token A token representing a FlowerRNG Sim state
-- @return a number as stated
-- @raise If called from a HUD hook or called with an invalid or HUD token.
-- @see FRNG.Sim_Create
function FRNG.Sim_GetSigned(token)
	return (generate_internal(token_to_state(token, false, 2)) & 0xFF) - 128
end

--- Get a random number between INT32_MIN and INT32_MAX.
-- @param token A token representing a FlowerRNG Sim state
-- @return a number as stated
-- @raise If called from a HUD hook or called with an invalid or HUD token.
-- @see FRNG.Sim_Create
function FRNG.Sim_GetInt32(token)
	return generate_internal(token_to_state(token, false, 2))
end

--- Get an array of random numbers between INT32_MIN and INT32_MAX.
-- @param token A token representing a FlowerRNG Sim state
-- @param count The number of random numbers needed.
-- @return an array count of random Int32s
-- @raise If called from a HUD hook or called with an invalid or HUD token.
-- @raise If count is not a number or is less than 0.
-- @see FRNG.Sim_Create, FRNG.Sim_GetInt32
function FRNG.Sim_GetInt32Array(token, count)
	return user_int32_array(token, false, count, 1)
end

--- Get a random number between 0 and range-1.
-- This function is not exactly identical to the M_RandomKey function. For one
-- thing numbers from 0 to INT32_MAX will work as you expect, but range is
-- treated as unsigned, so the numbers generated will wrap around past
-- INT32_MAX.
-- @param token A token representing a FlowerRNG Sim state
-- @param range The maximum value to return+1.
-- @return a number as stated
-- @raise If not called or called with an invalid or HUD token.
-- @raise If range is 0 or not a number.
-- @see FRNG.Sim_Create, FRNG.Sim_GetZeroToLimit
function FRNG.Sim_GetKey(token, range)
	return user_key(token, false, range, 1)
end

--- Get a random number between 0 and limit, inclusive.
-- The number is treated as signed.
-- @param token A token representing a FlowerRNG Sim state
-- @param range The maximum, or if negative minimum, value to return.
-- @return a number as stated
-- @raise If called from a HUD hook or called with an invalid or HUD token.
-- @raise If limit is 0 or not a number.
-- @see FRNG.Sim_Create, FRNG.Sim_GetKey
function FRNG.Sim_GetZeroToLimit(token, limit)
	return user_limit(token, false, limit, 1)
end

--- Get a random number between minimum and maximum, inclusive.
-- If maximum is less than minimum, wraparound must be set to true, and the
-- results will exclude the numbers between minimum and maximum treated as
-- unsigned integers. (This behavior is disabled by default because it's weird.)
-- @param token A token representing a FlowerRNG Sim state
-- @param minimum The minimum value to return.
-- @param maximum The maximum value to return.
-- @param wraparound Whether to allow wraparound. Defaults to false.
-- @raise If called from a HUD hook or called with an invalid or HUD token.
-- @raise If minimum or maximum is not a number.
-- @raise If maximum is less than minimum and wraparound is false or nil.
function FRNG.Sim_GetRange(token, minimum, maximum, wraparound)
	return user_between(token, false, minimum, maximum, wraparound, 1)
end

--- Get an approximately normally distributed fixed point number.
-- The higher the degree, the better the approximation of a normally distributed
-- number and the further from 0 the upper and lower limit of this number are.
-- @param token A token representing a FlowerRNG Sim state.
-- @param iterations The number of iterations to run. Optional, minimum is 6.
-- @raise If called from a HUD hook or called with an invalid or HUD token.
-- @see FRNG.Sim_Create
function FRNG.Sim_GetApproxNormal(token, iterations)
	return user_normal(token, false, iterations, 1)
end

--- Shuffles a table in place.
-- Only the array part of the table will be shuffled.
-- @param token A token representing a FlowerRNG HUD state
-- @param shuffle_table A table to shuffle.
-- @return nothing
-- @raise If called from a HUD hook or called with an invalid or HUD token.
-- @raise If shuffle_table is not a table.
function FRNG.Sim_Shuffle(token, shuffle_table)
	return user_shuffle(token, false, shuffle_table, 1)
end

--- Gets version information about FlowerRNG.
-- Semantic versioning is used, so if the major version number has not changed
-- your code should not break.
-- @return An array containing three numbers corresponding to the major, minor, and patch versions.
function FRNG.GetVersion()
	return {2, 0, 0}
end

rawset(_G,"FRNG",FRNG)   T  LUA_FRNG