1// Package prorata splits an integer amount across weighted claimants without2// leaking or inventing a unit.3//4// Every payout in a game is this operation: a pot, a roster, and a weight each.5// Written the obvious way, `amount*weight/total` per claimant, it is wrong in6// two ways that only show up with real money in the contract. The shares are7// each rounded down, so their sum is short of the amount by up to one unit per8// claimant, and that dust either accumulates in the contract forever or gets9// handed to whoever the code happens to pay last. And `amount*weight` overflows10// an int64 long before either factor does, which turns a large payout negative.11//12// Split fixes both. It distributes by largest remainder: floor every share,13// then hand the leftover units out one at a time to the claimants whose14// truncated fraction was largest, ties going to the lower index. The result15// sums to EXACTLY the amount, every time, and the rule is deterministic, so16// every node computes the same split and a Render of it does not change between17// calls.18//19// Nothing here reads the chain and nothing holds coins: the caller owns the20// roster and the custody. A game built on this package is at21// [r/moul/x/games/lastwords](/r/moul/x/games/lastwords/v0).22package prorata2324import (25 "errors"26 "sort"27)2829const maxInt64 = int64(9223372036854775807)3031var (32 // ErrNegativeAmount is returned when the amount to split is negative.33 ErrNegativeAmount = errors.New("prorata: amount must not be negative")34 // ErrNegativeWeight is returned when any weight is negative.35 ErrNegativeWeight = errors.New("prorata: weights must not be negative")36 // ErrNoWeight is returned when there is nobody to pay, or every weight is37 // zero. The caller must decide where the amount goes instead: silently38 // returning an empty split would strand it.39 ErrNoWeight = errors.New("prorata: total weight is zero, nothing to split across")40 // ErrOverflow is returned when the arithmetic does not fit in an int64.41 ErrOverflow = errors.New("prorata: weights overflow int64")42)4344// Split divides amount across weights and returns one share per weight, in the45// same order. The shares sum to exactly amount.46//47// A zero weight is allowed and receives nothing, including no remainder unit:48// somebody with no claim is not paid dust.49func Split(amount int64, weights []int64) ([]int64, error) {50 if amount < 0 {51 return nil, ErrNegativeAmount52 }53 total, err := Total(weights)54 if err != nil {55 return nil, err56 }57 if total == 0 {58 return nil, ErrNoWeight59 }6061 shares := make([]int64, len(weights))62 if amount == 0 {63 return shares, nil64 }6566 // Floor each share, and keep the truncated numerator to rank by.67 rems := make([]entry, 0, len(weights))68 assigned := int64(0)69 for i, w := range weights {70 if w == 0 {71 continue72 }73 share, rem, err := divide(amount, w, total)74 if err != nil {75 return nil, err76 }77 shares[i] = share78 assigned += share79 rems = append(rems, entry{index: i, rem: rem})80 }8182 // Hand the leftover out by largest remainder. There are strictly fewer83 // leftover units than claimants, so one pass over the ranking is enough.84 left := amount - assigned85 if left <= 0 {86 return shares, nil87 }88 sort.Sort(byRemainder(rems))89 for i := 0; i < len(rems) && left > 0; i++ {90 shares[rems[i].index]++91 left--92 }93 return shares, nil94}9596// Share returns what one weight is owed out of amount, rounded down. It is the97// "what would I get" query, and deliberately does NOT account for the98// remainder: use Split when the shares have to add up.99func Share(amount, weight, total int64) (int64, error) {100 if amount < 0 {101 return 0, ErrNegativeAmount102 }103 if weight < 0 || total < 0 {104 return 0, ErrNegativeWeight105 }106 if total == 0 {107 return 0, ErrNoWeight108 }109 if weight > total {110 weight = total111 }112 share, _, err := divide(amount, weight, total)113 return share, err114}115116// Total sums weights, refusing an int64 overflow rather than wrapping into a117// negative total that would make every share nonsense.118func Total(weights []int64) (int64, error) {119 sum := int64(0)120 for _, w := range weights {121 if w < 0 {122 return 0, ErrNegativeWeight123 }124 if w > maxInt64-sum {125 return 0, ErrOverflow126 }127 sum += w128 }129 return sum, nil130}131132// divide returns amount*weight/total rounded down, plus the remainder of that133// division, without ever computing amount*weight.134//135// It splits the amount into whole multiples of total and what is left over:136// amount = q*total + r, so amount*weight/total is exactly q*weight +137// r*weight/total. The first term is exact and the second multiplies a value138// already smaller than total, which is what keeps the product in range.139func divide(amount, weight, total int64) (share, rem int64, err error) {140 q := amount / total141 r := amount % total142 if weight != 0 && q > maxInt64/weight {143 return 0, 0, ErrOverflow144 }145 whole := q * weight146 if weight != 0 && r > maxInt64/weight {147 return 0, 0, ErrOverflow148 }149 part := r * weight150 if whole > maxInt64-part/total {151 return 0, 0, ErrOverflow152 }153 return whole + part/total, part % total, nil154}155156// entry is one claimant's truncated fraction, for ranking the leftover.157type entry struct {158 index int159 rem int64160}161162// byRemainder ranks by largest truncated remainder, ties by lowest index, so163// the split is identical on every node.164type byRemainder []entry165166func (b byRemainder) Len() int { return len(b) }167func (b byRemainder) Swap(i, j int) { b[i], b[j] = b[j], b[i] }168func (b byRemainder) Less(i, j int) bool {169 if b[i].rem != b[j].rem {170 return b[i].rem > b[j].rem171 }172 return b[i].index < b[j].index173}174Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.