Anarchy32

Contents

• Utility Functions
• Random Number Generator Functions
• Cohort Functions
• Distribution Functions

Libraries

• anarchy32

Examples

• test_anarchy32.lua

Module anarchy32

anarchy32.lua

Reversible chaos library (Lua 32-bit version for Lua 5.1, 5.2, and LuaJIT).

Info:

• Copyright: 2025 Peter Mawhorter
• Release: 1.0-1

  This version effectively uses 32-bit integers via the 'bit' or 'bit32' library, since Lua < 5.3 and LuaJIT don't have bitwise operations, and use 32-bit integers stored as floating point numbers. Use the 'anarchy' library instead if you have access to Lua 5.3+.

  Note: In LuaJIT, 'bit' is available via 'require' for 32-bit bitwise operations. In Lua 5.1, a backport of the Lua 5.2 bit32 library could be installed as a dependency. In Lua 5.2, 'bit32' is built-in. In Lua 5.3+, 'bit32' is deprecated and we get 64-bit integers plus built-in bitwise operations (you'll need the 'anarchy' module instead, which is the 64-bit version)!

  It might make sense to depend on Lua 5.3+ and use the built-ins, but many modding situations have older Lua versions tied into engines. So we awkwardly try to support all of these different options...

  See more details in the README file.

• Author: Peter Mawhorter

Utility Functions

Random Number Generator Functions

Cohort Functions

Distribution Functions

Utility Functions

anarchy.util.posmod (num, base)

Modulus that's always positive Use % operator instead in Lua since it has the same behavior Included for compatibility with anarchy implementations in other languages.

Parameters:

• num number The number to compute the modulus of.
• base number The base of the modulus.

Returns:

number The number modulo the base.

anarchy.util.hash_string (s)

A string hashing function. See: https://stackoverflow.com/questions/7616461/generate-a-hash-from-string-in-javascript-jquery

Parameters:

• s string The string to hash

Returns:

number The hash for that string

anarchy.util.mask (bits)

Creates a mask with the given number of 1 bits. Avoids shift operator because of 32-bit limit, but watch out for floating point behavior for bit amounts greater than ~52

Parameters:

• bits number The number of 1 bits to put in the mask.

Returns:

number A value with that many 1 bits starting from the least significant place. Won't work for large numbers of bits.

anarchy.util.byte_mask (n)

Returns a mask that covers just the nth byte (zero-indexed), starting from the least-significant digits. Starts to break down when it exceeds ~52 bits (byte 6 or so).

Parameters:

• n number The byte index (starting from 0)

Returns:

number The mask with 1s in that byte and 0s elsewhere

Random Number Generator Functions

anarchy.rng.swirl (x, distance)

Circular bit shift to the right Distance is capped at 3/4 of ID_BITS

Parameters:

• x number The number to swirl.
• distance number How far to swirl it.

Returns:

number The swirled number.

anarchy.rng.rev_swirl (x, distance)

Circular bit shift to the left inverse of swirl Distance is capped at 3/4 of ID_BITS

Parameters:

• x number The number to unswirl.
• distance number How far to unswirl it.

Returns:

number The unswirled number.

anarchy.rng.fold (x, where)

Folds lower bits into upper bits using xor. fold is its own inverse. 'where' is restricted to fall between 1/4 and 1/2 of ID_BITS.

Parameters:

• x number the number to fold.
• where number which tit to fold at

anarchy.rng.flop (x)

Flops each 1/2 byte with the adjacent 1/2 byte. flop is its own inverse.

Parameters:

• x number the number to flop

Returns:

number The flopped number

anarchy.rng.scramble (x)

Implements a reversible linear-feedback-shift-register-like operation.

Parameters:

• x number the number to scramble.

Returns:

number the scrambled number

anarchy.rng.rev_scramble (x)

Inverse of scramble (see above).

Parameters:

• x number the number to unscramble

Returns:

number the unscrambled number

anarchy.rng.scramble_seed (s)

Scrambles a seed value to help separate RNG sequences generated from sequential seeds.

Parameters:

• s number the seed to scramble

Returns:

number the scrambled seed

anarchy.rng.prng (x, seed)

A simple reversible pseudo-random number generator You can call anarchy.rng.rev_prng with the result of this function and the same seed to get back the number you put in here, so that results form a chain you can traverse forwards or backwards.

Parameters:

• x number the current/previous number
• seed number the generation sequence seed (this can be constant for a bunch of calls)

Returns:

number the next number in the generation sequence

anarchy.rng.rev_prng (x, seed)

Inverse of anarchy.rng.prng (see above).

Parameters:

• x number the current/next number
• seed number the generation seed that determines the sequence

Returns:

number the previous number in the generation sequence

anarchy.rng.lfsr (x)

Implements a max-cycle-length 32-bit linear feedback shift register. See: https://en.wikipedia.org/wiki/Linear-feedbackshiftregister Note that this is NOT reversible! Note: Do not use this as an irreversible PRNG; it's a terrible one! Note: Zero is a fixed point of this function: do not use it as your seed!

Parameters:

• x number the current number

Returns:

number the next number in the LFSR sequence

anarchy.rng.uniform (seed)

Generates a random number between 0 and 1 given a seed value.

Parameters:

• seed number The seed that determines the result.

Returns:

number A number between 0 (inclusive) and 1 (exclusive)

anarchy.rng.normalish (seed)

Generates and averages three random numbers between 0 and 1 to give a pseudo-gaussian-distributed random number (still strictly on [0, 1) )

Parameters:

• seed number The seed that determines the result.

Returns:

number A number between 0 (inclusive) and 1 (exclusive) which is more likely to be near 0.5 than near either 0 or 1.

anarchy.rng.flip (p, seed)

Flips a coin with probability p of being True. Using the same seed always gives the same result.

Parameters:

• p number The probability that the result should be True when results are averaged across many different seeds.
• seed number The seed that determines the result.

Returns:

boolean Either true (with probability p when averaged across seeds) or false (with probability 1-p when averaged across seeds).

anarchy.rng.integer (seed, start, cap)

Even distribution over the given integer range, including the start but excluding the cap (even if the cap is lower than the start). The last number before the cap is about 1/2^31 less likely to be generated than the other numbers.

Parameters:

• seed number The seed that determines the result.
• start number The minimum allowed result value.
• cap number The result limit (will NOT ever be generated itself).

Returns:

number An integer between start (inclusive) and cap (exclusive).

anarchy.rng.exponential (seed, lambda)

Generates a number from an exponential distribution on [0,∞) with mean 1/lambda given a seed. Higher values of lambda make the distribution more sharply exponential; values between 0.5 and 1.5 exhibit reasonable variation. See: https://math.stackexchange.com/questions/28004/random-exponential-like-distribution and https://en.wikipedia.org/wiki/Exponential_distribution

Parameters:

• seed number The seed that determines the result.
• lambda number The shape parameter for the distribution.

Returns:

number An arbitrarily large number (subject to the limits of the number type) that's much more likely to be small than large.

anarchy.rng.truncated_exponential (seed, lambda)

Generates a number from a truncated exponential distribution on [0, 1), given a particular seed. As with expdist, the lambda parameter controls the shape of the distribution, and a 0.5–1.5 range is usually reasonable. For why this method works, see: https://math.stackexchange.com/questions/28004/random-exponential-like-distribution

Parameters:

• seed number The seed that determines the result.
• lambda number The shape parameter for the distribution.

Returns:

number A number between 0 (inclusive) and 1 (exclusive) that is much more likely to be small than large.

Cohort Functions

anarchy.cohort.cohort (outer, cohort_size)

Computes cohort number for the given outer index and cohort size.

Parameters:

• outer number An index into a sequence to be chopped into cohorts, starting with the beginning of the first cohort at index 1.
• cohort_size number The size of each cohort to divide the sequence into.

Returns:

number The index of the cohort that the outer index falls into. The first cohort (starting at index 1 of the outer sequence) has index 1.

For example, if outer index is 54 and cohort_size is 10, the return value will be 6, since 54 falls into the 6th group of 10.

anarchy.cohort.cohort_inner (outer, cohort_size)

Computes within-cohort index for the given outer index and cohorts of the given size.

Parameters:

• outer number An index into a sequence to be chopped into cohorts, starting with the beginning of the first cohort at index 1.
• cohort_size number The size of each cohort to divide the sequence into.

Returns:

number The index of the given outer index within its cohort, starting from 1 in the first position.

For example, if the outer index is 54 and the cohort_size is 10, the result will be 4, since 54 falls at index 4 within its group of 10 (starting at index 1 at 51).

anarchy.cohort.cohort_and_inner (outer, cohort_size)

Returns two results: the cohort number and inner index for the given outer index and cohort size. inner index within that cohort (also an integer).

For example, if the outer index is 29 and the cohort_size is 10, this will return 3, 9

Parameters:

• outer number An index into a sequence to be chopped into cohorts.
• cohort_size number The size of each cohort to divide the sequence into.

Returns:

Multiple values: The cohort index (an integer) followed by the

anarchy.cohort.cohort_outer (cohort, inner, cohort_size)

Inverse of cohortandinner; computes the outer index from a cohort number and inner index.

Parameters:

• cohort number The cohort index determining which group a position belongs to.
• inner number The index of the position within that group. Should be between 1 and the cohort size, inclusive.
• cohort_size number The size of each group to divide the total sequence of positions into.

Returns:

number The index of that position within the total sequence of positions, starting from index 1.

For example, if cohort is 3, inner is 1, and cohort_size is 5, then we're at index 1 (1st item) within the 3th group of 5 things, putting us at total index 5*2 + 1 = 11 outside of the groups.

Note: Negative cohort and/or inner indices may result in negative outer indices. The inner index value is not constrained to be smaller than the cohort size.

anarchy.cohort.cohort_interleave (inner, cohort_size)

Interleaves cohort members by folding the top half into the bottom half. The bottom half get even indices while the top half are assigned backwards to the odd indices.

Parameters:

• inner number The index of an item within a cohort.
• cohort_size number The size of each cohort.

Returns:

number The new within-cohort index for the same item after interleaving the top and bottom parts of the cohort.

anarchy.cohort.rev_cohort_interleave (inner, cohort_size)

Inverse interleave (see above).

Parameters:

• inner number The index of an item within a cohort after interleaving items.
• cohort_size number The size of each cohort.

Returns:

number The original index within that cohort that the item would have been at prior to interleaving things.

anarchy.cohort.cohort_fold (inner, cohort_size, seed)

Folds items past an arbitrary split point (in the second half of the cohort) into the middle of the cohort. The split will always leave an odd number at the end.

Parameters:

• inner number The index of an item within a cohort.
• cohort_size number The size of each cohort.
• seed number The seed that determines where the fold happens.

Returns:

number The new index of the item within the cohort after folding.

anarchy.cohort.rev_cohort_fold (inner, cohort_size, seed)

Inverse fold (see above).

Parameters:

• inner number The index of an item within a cohort after folding.
• cohort_size number The size of each cohort.
• seed number The seed that determines where the fold happened.

Returns:

number The original index that would have been folded into the given position if cohort_fold were used with the same seed..

anarchy.cohort.cohort_spin (inner, cohort_size, seed)

Applies a circular offset

Parameters:

• inner number The index of an item within a cohort.
• cohort_size number The size of each cohort.
• seed number The seed that determines how far to spin.

Returns:

number The index of the item after spinning.

anarchy.cohort.rev_cohort_spin (inner, cohort_size, seed)

Inverse spin (see above).

Parameters:

• inner number The index of an item within a cohort after being spun.
• cohort_size number The size of each cohort.
• seed number The seed that determined how far to spin.

Returns:

number The original index of the item before spinning.

anarchy.cohort.cohort_flop (inner, cohort_size, seed)

Flops sections (with seeded sizes) with their neighbors.

Parameters:

• inner number The index of an item within a cohort.
• cohort_size number The size of each cohort.
• seed number The seed that determines how big each section to flop is.

Returns:

number The index of the item after flopping with a neighboring sesction.

anarchy.cohort.cohort_mix (inner, cohort_size, seed)

Applies a spin to even and odd items separately with different seeds.

Parameters:

• inner number The index of an item within a cohort.
• cohort_size number The size of each cohort.
• seed number The seed that determines how far to spin evens & odds.

Returns:

number The index of the item after spinning the even & odd elements among themselves with different (derived) seeds.

anarchy.cohort.rev_cohort_mix (inner, cohort_size, seed)

Inverse mix (see above).

Parameters:

• inner number The index of an item within a cohort after mixing.
• cohort_size number The size of each cohort.
• seed number The seed that determined how far to spin evens & odds.

Returns:

number The index that this index would have been before mixing with the given seed.

anarchy.cohort.cohort_spread (inner, cohort_size, seed)

Spreads items out between a random number of different regions within the cohort.

Parameters:

• inner number The index of an item within a cohort.
• cohort_size number The size of each cohort.
• seed number The seed that determines how many regions we use.

Returns:

number The index after spreading out indices between random regions.

anarchy.cohort.rev_cohort_spread (inner, cohort_size, seed)

Inverse spread (see above).

Parameters:

• inner number The index of an item within a cohort after spreading.
• cohort_size number The size of each cohort.
• seed number The seed that determined how many regions we use.

Returns:

number The index that would have been used to generate the provided index with a spread operation and the given seed.

anarchy.cohort.cohort_upend (inner, cohort_size, seed)

Reverses ordering within each of several fragments.

Parameters:

• inner number The index of an item within a cohort.
• cohort_size number The size of each cohort.
• seed number The seed that determined how many regions we use.

Returns:

number The index after upending the order of each region.

anarchy.cohort.cohort_shuffle (inner, cohort_size, seed)

Compose a bunch of the above functions to perform a nice thorough shuffle within a cohort.

Parameters:

• inner number The index of an item within a cohort.
• cohort_size number The size of each cohort.
• seed number The seed that determines where to shuffle things.

Returns:

number The position of the index after shuffling the cohort. When shuffling two different indices with the same cohort size and seed, you'll get two different results. Usually not the same as the original index.

anarchy.cohort.rev_cohort_shuffle (inner, cohort_size, seed)

Inverse shuffle (see above).

Parameters:

• inner number The index of an item within a cohort after shuffling.
• cohort_size number The size of each cohort.
• seed number The seed that determined where to shuffle things.

Returns:

number The original index within the cohort that would have been shuffled into the specified position.

Distribution Functions

anarchy.distribution.distribution_split_point (total, n_segments, segment_capacity, roughness, seed)

Implements common distribution functionality: given a total item count, a segment count and per-segment capacity, and a roughness value and seed, computes the split point for the items as well as the halfway index for the segments.

Note that per the normal Lua convention, indices for both total items and segments start from 1!

for the distribution: the number out of the total items which end up in the first half of the segments. The second is the number of segments in that first half of the segments, which is half of n_segments, rounded down.

Parameters:

• total number The total number of items that will be distributed among segments.
• n_segments number The number of segments to distribute the items into.
• segment_capacity number The capacity of each segment. nsegments times segmentcapacity must be >= total.
• roughness number A number between 0 and 1. When roughness is 0, items will be split across segments as evenly as possible. When roughness is 1, up to 100% of the items may be placed into the first or second half of the segments while recursively apportioning items. At roughness 0.5 the first or second half of the segments might get as little as 50% of what it would get when roughness is 0.
• seed number The seed that determines how the total gets distributed among the segments when roughness allows different distributions.

Returns:

Multiple results: two numbers. The first is the split point

anarchy.distribution.distribution_items (segment, total, n_segments, segment_capacity, roughness, seed)

Given that 'total' items are to be distributed evenly among 'nsegment' segments each with at most 'segmentcapacity' items and we're in segment 'segment' of those (indexed from 1), computes the start index (from 1) among the total of the first item in this segment, and how many items are in this segment. The 'roughness' argument should be a number between 0 and 1 indicating how even the distribution is: 0 indicates a perfectly even distribution, while 1 indicates a perfectly random distribution. Does work proportional to the log of the number of segments.

Note that segmentcapacity * nsegments should be > total.

this segment and the number of the total items that get distributed into the specified segment, for the given seed. The number of items May be as low as 0 when roughness is 1; it will be one of the integers adjacent to (total / n_segments) when roughness is 0. If the number of items is 0, then the 'start index' will be the same as the 'start index' for the subsequent segment (and if multiple segments in a row get 0 items they'll all share the same start index with the first segment after them that gets at least 1 item).

Parameters:

• segment number Which segment we want to know the portion for, as an index starting from 1.
• total number The total number of items that will be distributed among segments.
• n_segments number The number of segments to distribute the items into.
• segment_capacity number The capacity of each segment. nsegments times segmentcapacity must be >= total.
• roughness number A number between 0 and 1. When roughness is 0, items will be split across segments as evenly as possible. When roughness is 1, up to 100% of the items may be placed into the first or second half of the segments while recursively apportioning items. At roughness 0.5 the first or second half of the segments might get as little as 50% of what it would get when roughness is 0.
• seed number The seed that determines how the total gets distributed among the segments when roughness allows different distributions.

Returns:

Multiple values: the start index (from 1) of the first item in

anarchy.distribution.distribution_segment (index, total, n_segments, segment_capacity, roughness, seed)

Computes the segment number in which a certain item appears (one of the 'total' items distributed between segments; see distribution_items above). Requires work proportional to the log of the number of segments.

which the indicated item appears, and then the index within that segment (starting from 1) at which it is placed.

Parameters:

• index number Which item among the total we want to know the fate of, starting from 1. Must be less than or equal to the total.
• total number The total number of items that will be distributed among segments.
• n_segments number The number of segments to distribute the items into.
• segment_capacity number The capacity of each segment. nsegments times segmentcapacity must be >= total.
• roughness number A number between 0 and 1. When roughness is 0, items will be split across segments as evenly as possible. When roughness is 1, up to 100% of the items may be placed into the first or second half of the segments while recursively apportioning items. At roughness 0.5 the first or second half of the segments might get as little as 50% of what it would get when roughness is 0.
• seed number The seed that determines how the total gets distributed among the segments when roughness allows different distributions.

Returns:

Multiple values: the segment index (starting from 1) within

anarchy.distribution.sumtable_for_distribution (total, n_segments, segment_capacity, roughness, seed)

Takes distribution parameters and returns a table containing the cumulative sum of items in each segment (The table indices will start at 1, just like the segment indices). The list contains n_segments entries, and each entry holds the sum of the items from the total assigned to that segment plus all earlier segments. This means that each entry is greater than or equal to the entry before it (and they're only equal if zero items are assigned to that segment). The last entry will be equal to the total.

Parameters:

• total number The total number of items being distributed.
• n_segments number The number of segments to distribute items among.
• segment_capacity number The capacity of each segment.
• roughness number How rough the distribution should be (0-1).
• seed number The seed that determines a specific distribution.

Returns:

table An array table holding cumulative sums, starting at index 1 with the number of items in the first segment.

n_segments times segment_capacity must be >= total otherwise an error will be raised.

anarchy.distribution.fill_sumtable_for_distribution (ledger, start, prior)

Recursively fills in the sumtable based on the distribution parameters given (see sumtable_for_distribution). Total work done is n_segments times log(n_segments).

Note that using a sumtable instead of using the distribution functions with the same parameters over and over again represents a space/time tradeoff. Most operations on a sumtable are O(1), where equivalent distribution functions need O(log(n)) time. The sumtable needs to store one integer per segment. The use of distribution functions is recommended primarily in situations where the algorithm structure makes it inconvenient to store the sumtable in an accessible way, so sharing parameters is easier. Parameters are the same as for sumtable_for_distribution but with:

Parameters:

• ledger table The table to fill in. Values will be added/overwritten between start and start + n_segments - 1 (inclusive).
• start number The index at which to start overwriting values (counting from index 1).
• prior number The number of items distributed prior to the start index.

Returns:

nil No return (modifies the given ledger).

anarchy.distribution.sumtable_from_portions (portions)

Returns a sumtable for the same distribution, where entries are the cumulative sum of all portions up to an index, rather than just the portion at that index. Use functions like sumtable_total, sumtable_segments, sumtable_portion, and sumtable_segment to get information out of the sumtable efficiently.

Parameters:

• portions table The array of per-segment item counts, indexed starting at 1.

Returns:

table The sumtable that encodes the same distribution (also indexed from 1, like all normal Lua tables. Hahaha why would we even mention this?).

anarchy.distribution.sumtable_total (sumtable)

Returns the total number of items across all segments in a sumtable, which is just the last entry in that table.

Parameters:

• sumtable table The table of sums describing the distribution in question.

Returns:

number The total number of items distributed.

anarchy.distribution.sumtable_segments (sumtable)

Returns the number of segments in the given sumtable, which is just its length.

Parameters:

• sumtable table The table of sums describing the distribution in question.

Returns:

number The number of segments in the distribution.

anarchy.distribution.sumtable_portion (sumtable, i)

Returns the portion of the total items which is distributed into the segment with the given index (starting from 1). Just needs to subtract the entry to the left to figure this out. Raises an error if the index is invalid.

Parameters:

• sumtable table The table of sums describing the distribution in question.
• i number The segment to compute the portion for (from 1).

Returns:

number The number of items distributed into the specified segment.

anarchy.distribution.sumtable_items (sumtable, i)

Returns a pair containing the index of the first item in the segment and then the number of items in that segment, like distribution_items, but for a sumtable. Parameters:

1), then the number o items in the indicated segment.

Parameters:

• sumtable table The table of sums describing the distribution in question.
• i number The segment to compute the portion for (from 1).

Returns:

Two numbers: The index of the first item in the segment (from

anarchy.distribution.sumtable_segment (sumtable, item)

Uses binary search to find the index of the smallest sum in the given sumtable that's greater than or equal to the given value breaking ties towards earlier entries. Works in time proportional to the logarithm of the sumtable size. This will be the segment which the given item (out of the total) falls into.

Raises an error if the sumtable is empty, or if the item index is too large for the sumtable or is zero or negative.

Parameters:

• sumtable table The table of sums describing the distribution in question.
• item number The item (out of the total distributed, starting from 0) that we want to find the segment for.

Returns:

number The segment index (starting from 1) for the specified item.