.. | .. |
---|
29 | 29 | #include <linux/types.h> |
---|
30 | 30 | |
---|
31 | 31 | #include "i915_random.h" |
---|
| 32 | +#include "i915_utils.h" |
---|
32 | 33 | |
---|
33 | 34 | u64 i915_prandom_u64_state(struct rnd_state *rnd) |
---|
34 | 35 | { |
---|
.. | .. |
---|
41 | 42 | return x; |
---|
42 | 43 | } |
---|
43 | 44 | |
---|
| 45 | +void i915_prandom_shuffle(void *arr, size_t elsz, size_t count, |
---|
| 46 | + struct rnd_state *state) |
---|
| 47 | +{ |
---|
| 48 | + char stack[128]; |
---|
| 49 | + |
---|
| 50 | + if (WARN_ON(elsz > sizeof(stack) || count > U32_MAX)) |
---|
| 51 | + return; |
---|
| 52 | + |
---|
| 53 | + if (!elsz || !count) |
---|
| 54 | + return; |
---|
| 55 | + |
---|
| 56 | + /* Fisher-Yates shuffle courtesy of Knuth */ |
---|
| 57 | + while (--count) { |
---|
| 58 | + size_t swp; |
---|
| 59 | + |
---|
| 60 | + swp = i915_prandom_u32_max_state(count + 1, state); |
---|
| 61 | + if (swp == count) |
---|
| 62 | + continue; |
---|
| 63 | + |
---|
| 64 | + memcpy(stack, arr + count * elsz, elsz); |
---|
| 65 | + memcpy(arr + count * elsz, arr + swp * elsz, elsz); |
---|
| 66 | + memcpy(arr + swp * elsz, stack, elsz); |
---|
| 67 | + } |
---|
| 68 | +} |
---|
| 69 | + |
---|
44 | 70 | void i915_random_reorder(unsigned int *order, unsigned int count, |
---|
45 | 71 | struct rnd_state *state) |
---|
46 | 72 | { |
---|
47 | | - unsigned int i, j; |
---|
48 | | - |
---|
49 | | - for (i = 0; i < count; i++) { |
---|
50 | | - BUILD_BUG_ON(sizeof(unsigned int) > sizeof(u32)); |
---|
51 | | - j = i915_prandom_u32_max_state(count, state); |
---|
52 | | - swap(order[i], order[j]); |
---|
53 | | - } |
---|
| 73 | + i915_prandom_shuffle(order, sizeof(*order), count, state); |
---|
54 | 74 | } |
---|
55 | 75 | |
---|
56 | 76 | unsigned int *i915_random_order(unsigned int count, struct rnd_state *state) |
---|
.. | .. |
---|
68 | 88 | i915_random_reorder(order, count, state); |
---|
69 | 89 | return order; |
---|
70 | 90 | } |
---|
| 91 | + |
---|
| 92 | +u64 igt_random_offset(struct rnd_state *state, |
---|
| 93 | + u64 start, u64 end, |
---|
| 94 | + u64 len, u64 align) |
---|
| 95 | +{ |
---|
| 96 | + u64 range, addr; |
---|
| 97 | + |
---|
| 98 | + BUG_ON(range_overflows(start, len, end)); |
---|
| 99 | + BUG_ON(round_up(start, align) > round_down(end - len, align)); |
---|
| 100 | + |
---|
| 101 | + range = round_down(end - len, align) - round_up(start, align); |
---|
| 102 | + if (range) { |
---|
| 103 | + addr = i915_prandom_u64_state(state); |
---|
| 104 | + div64_u64_rem(addr, range, &addr); |
---|
| 105 | + start += addr; |
---|
| 106 | + } |
---|
| 107 | + |
---|
| 108 | + return round_up(start, align); |
---|
| 109 | +} |
---|