aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMax <msuraev@sysmocom.de>2018-02-05 16:15:30 +0100
committerHarald Welte <laforge@gnumonks.org>2018-02-21 12:08:40 +0000
commit731e2bb328f6b0d739fa21913eb30cff8a46c70c (patch)
tree2c82ae7d2b9ae6317b2a08c1fe6ce06bef458752
parent77988d469d5cd0d876188a829b93890049cc6830 (diff)
Simplify TS alloc: move slot check into functions
Move timeslot applicability check outside of nested for loop into separate functions and document them. Add corresponding tests. This allows us to clarify types used in TS-related computations. Change-Id: Ic39e848da47dc11357782362fdf6206d2c1457c2 Related: OS#2282
-rw-r--r--src/gprs_rlcmac_ts_alloc.cpp188
-rw-r--r--src/mslot_class.c35
-rw-r--r--src/mslot_class.h3
-rw-r--r--tests/alloc/MslotTest.cpp10
-rw-r--r--tests/alloc/MslotTest.ok513
5 files changed, 626 insertions, 123 deletions
diff --git a/src/gprs_rlcmac_ts_alloc.cpp b/src/gprs_rlcmac_ts_alloc.cpp
index 4cc95392..835c199b 100644
--- a/src/gprs_rlcmac_ts_alloc.cpp
+++ b/src/gprs_rlcmac_ts_alloc.cpp
@@ -54,19 +54,11 @@ static char *set_flag_chars(char *buf, uint8_t val, char set_char, char unset_ch
return buf;
}
-static bool test_and_set_bit(uint32_t *bits, size_t elem)
-{
- bool was_set = bits[elem/32] & (1 << (elem % 32));
- bits[elem/32] |= (1 << (elem % 32));
-
- return was_set;
-}
-
-static int find_possible_pdchs(const struct gprs_rlcmac_trx *trx, size_t max_slots, uint8_t mask,
- const char *mask_reason = NULL)
+static uint8_t find_possible_pdchs(const struct gprs_rlcmac_trx *trx, uint8_t max_slots, uint8_t mask,
+ const char *mask_reason = NULL)
{
unsigned ts;
- int valid_ts_set = 0;
+ uint8_t valid_ts_set = 0;
int8_t last_tsc = -1; /* must be signed */
for (ts = 0; ts < ARRAY_SIZE(trx->pdch); ts++) {
@@ -353,7 +345,7 @@ int alloc_algorithm_a(struct gprs_rlcmac_bts *bts, GprsMs *ms_, struct gprs_rlcm
int trx_no;
int tfi = -1;
int usf = -1;
- int mask = 0xff;
+ uint8_t mask = 0xff;
const char *mask_reason = NULL;
const GprsMs *ms = ms_;
const gprs_rlcmac_tbf *tbf = tbf_;
@@ -457,6 +449,58 @@ static inline unsigned compute_capacity(const struct gprs_rlcmac_trx *trx, int r
return capacity;
}
+/*! Decide if a given slot should be skipped by multislot allocator
+ *
+ * \param[in] ms_class Pointer to MS Class object
+ * \param[in] check_tr Flag indicating whether we should check for Tra or Tta parameters for a given MS class
+ * \param[in] rx_window Receive window
+ * \param[in] tx_window Transmit window
+ * \param[in,out] checked_rx array with already checked RX timeslots
+ * \returns true if the slot should be skipped, false otherwise
+ */
+static bool skip_slot(uint8_t mslot_class, bool check_tr,
+ int16_t rx_window, int16_t tx_window,
+ uint32_t *checked_rx)
+{
+ uint8_t common_slot_count, req_common_slots,
+ rx_slot_count = pcu_bitcount(rx_window),
+ tx_slot_count = pcu_bitcount(tx_window);
+
+ /* Check compliance with TS 45.002, table 6.4.2.2.1 */
+ /* Whether to skip this round doesn not only depend on the bit
+ * sets but also on check_tr. Therefore this check must be done
+ * before doing the mslot_test_and_set_bit shortcut. */
+ if (mslot_class_get_type(mslot_class) == 1) {
+ uint16_t slot_sum = rx_slot_count + tx_slot_count;
+ /* Assume down + up / dynamic.
+ * TODO: For ext-dynamic, down only, up only add more cases.
+ */
+ if (slot_sum <= 6 && tx_slot_count < 3) {
+ if (!check_tr)
+ return true; /* Skip Tta */
+ } else if (slot_sum > 6 && tx_slot_count < 3) {
+ if (check_tr)
+ return true; /* Skip Tra */
+ } else
+ return true; /* No supported row in TS 45.002, table 6.4.2.2.1. */
+ }
+
+ /* Avoid repeated RX combination check */
+ if (mslot_test_and_set_bit(checked_rx, rx_window))
+ return true;
+
+ /* Check number of common slots according to TS 45.002, ยง6.4.2.2 */
+ common_slot_count = pcu_bitcount(tx_window & rx_window);
+ req_common_slots = OSMO_MIN(tx_slot_count, rx_slot_count);
+ if (mslot_class_get_type(mslot_class) == 1)
+ req_common_slots = OSMO_MIN(req_common_slots, 2);
+
+ if (req_common_slots != common_slot_count)
+ return true;
+
+ return false;
+}
+
/*! Find set of slots available for allocation while taking MS class into account
*
* \param[in] trx Pointer to TRX object
@@ -468,16 +512,12 @@ static inline unsigned compute_capacity(const struct gprs_rlcmac_trx *trx, int r
int find_multi_slots(struct gprs_rlcmac_trx *trx, uint8_t mslot_class, uint8_t *ul_slots, uint8_t *dl_slots)
{
uint8_t Tx = mslot_class_get_tx(mslot_class), /* Max number of Tx slots */
- Sum = mslot_class_get_sum(mslot_class); /* Max number of Tx + Rx slots */
- int rx_window, tx_window, pdch_slots;
+ Sum = mslot_class_get_sum(mslot_class), /* Max number of Tx + Rx slots */
+ max_slots, num_tx, mask_sel, pdch_slots, ul_ts, dl_ts;
+ int16_t rx_window, tx_window;
char slot_info[9] = {0};
int max_capacity = -1;
uint8_t max_ul_slots = 0, max_dl_slots = 0;
- unsigned max_slots;
-
- unsigned ul_ts, dl_ts;
- unsigned num_tx;
- unsigned mask_sel;
if (mslot_class)
LOGP(DRLCMAC, LOGL_DEBUG, "Slot Allocation (Algorithm B) for class %d\n",
@@ -519,13 +559,11 @@ int find_multi_slots(struct gprs_rlcmac_trx *trx, uint8_t mslot_class, uint8_t *
/* Rotate group of TX slots: UUU-----, -UUU----, ..., UU-----U */
for (ul_ts = 0; ul_ts < 8; ul_ts += 1, tx_valid_win <<= 1) {
- unsigned tx_slot_count;
- int max_rx;
uint16_t rx_valid_win;
uint32_t checked_rx[256/32] = {0};
/* Wrap valid window */
- tx_valid_win = (tx_valid_win | tx_valid_win >> 8) & 0xff;
+ tx_valid_win = mslot_wrap_window(tx_valid_win);
tx_window = tx_valid_win;
@@ -540,10 +578,7 @@ int find_multi_slots(struct gprs_rlcmac_trx *trx, uint8_t mslot_class, uint8_t *
if ((tx_window & (1 << ((ul_ts+num_tx-1) % 8))) == 0)
continue;
- tx_slot_count = pcu_bitcount(tx_window);
-
- max_rx = OSMO_MIN(mslot_class_get_rx(mslot_class), Sum - num_tx);
- rx_valid_win = (1 << max_rx) - 1;
+ rx_valid_win = (1 << OSMO_MIN(mslot_class_get_rx(mslot_class), Sum - num_tx)) - 1;
/* Rotate group of RX slots: DDD-----, -DDD----, ..., DD-----D */
for (dl_ts = 0; dl_ts < 8; dl_ts += 1, rx_valid_win <<= 1) {
@@ -552,107 +587,14 @@ int find_multi_slots(struct gprs_rlcmac_trx *trx, uint8_t mslot_class, uint8_t *
/* Validate with both Tta/Ttb/Trb and Ttb/Tra/Trb */
for (mask_sel = MASK_TT; mask_sel <= MASK_TR; mask_sel += 1) {
- unsigned common_slot_count;
- unsigned req_common_slots;
- unsigned rx_slot_count;
- uint16_t rx_bad;
- uint8_t rx_good;
int capacity;
- /* Filter out bad slots */
- rx_bad = (uint16_t)(0xff & ~rx_mask[mask_sel]) << ul_ts;
- rx_bad = (rx_bad | (rx_bad >> 8)) & 0xff;
- rx_good = *dl_slots & ~rx_bad;
-
- /* TODO: CHECK this calculation -> separate function for unit
- * testing */
-
- rx_window = rx_good & rx_valid_win;
- rx_slot_count = pcu_bitcount(rx_window);
-
-#if 0
- LOGP(DRLCMAC, LOGL_DEBUG, "n_tx=%d, n_rx=%d, mask_sel=%d, "
- "tx=%02x, rx=%02x, mask=%02x, bad=%02x, good=%02x, "
- "ul=%02x, dl=%02x\n",
- tx_slot_count, rx_slot_count, mask_sel,
- tx_window, rx_window, rx_mask[mask_sel], rx_bad, rx_good,
- *ul_slots, *dl_slots);
-#endif
-
- /* Check compliance with TS 45.002, table 6.4.2.2.1 */
- /* Whether to skip this round doesn not only depend on the bit
- * sets but also on mask_sel. Therefore this check must be done
- * before doing the test_and_set_bit shortcut. */
- if (mslot_class_get_type(mslot_class) == 1) {
- unsigned slot_sum = rx_slot_count + tx_slot_count;
- /* Assume down+up/dynamic.
- * TODO: For ext-dynamic, down only, up only add more
- * cases.
- */
- if (slot_sum <= 6 && tx_slot_count < 3) {
- if (mask_sel != MASK_TR)
- /* Skip Tta */
- continue;
- } else if (slot_sum > 6 && tx_slot_count < 3) {
- if (mask_sel != MASK_TT)
- /* Skip Tra */
- continue;
- } else {
- /* No supported row in table 6.4.2.2.1. */
-#ifdef ENABLE_TS_ALLOC_DEBUG
- LOGP(DRLCMAC, LOGL_DEBUG,
- "- Skipping DL/UL slots: (TS=0)\"%s\"(TS=7), "
- "combination not supported\n",
- set_flag_chars(set_flag_chars(set_flag_chars(
- slot_info,
- rx_bad, 'x', '.'),
- rx_window, 'D'),
- tx_window, 'U'));
-#endif
- continue;
- }
- }
-
- /* Avoid repeated RX combination check */
- if (test_and_set_bit(checked_rx, rx_window))
+ rx_window = mslot_filter_bad(rx_mask[mask_sel], ul_ts, *dl_slots, rx_valid_win);
+ if (rx_window < 0)
continue;
- if (!rx_good) {
-#ifdef ENABLE_TS_ALLOC_DEBUG
- LOGP(DRLCMAC, LOGL_DEBUG,
- "- Skipping DL/UL slots: (TS=0)\"%s\"(TS=7), "
- "no DL slots available\n",
- set_flag_chars(set_flag_chars(slot_info,
- rx_bad, 'x', '.'),
- tx_window, 'U'));
-#endif
- continue;
- }
-
- if (!rx_window)
- continue;
-
- /* Check number of common slots according to TS 54.002, 6.4.2.2 */
- common_slot_count = pcu_bitcount(tx_window & rx_window);
- req_common_slots = OSMO_MIN(tx_slot_count, rx_slot_count);
- if (mslot_class_get_type(mslot_class) == 1)
- req_common_slots = OSMO_MIN(req_common_slots, 2);
-
- if (req_common_slots != common_slot_count) {
-#ifdef ENABLE_TS_ALLOC_DEBUG
- LOGP(DRLCMAC, LOGL_DEBUG,
- "- Skipping DL/UL slots: (TS=0)\"%s\"(TS=7), "
- "invalid number of common TS: %d (expected %d)\n",
- set_flag_chars(set_flag_chars(set_flag_chars(
- slot_info,
- rx_bad, 'x', '.'),
- rx_window, 'D'),
- tx_window, 'U'),
- common_slot_count,
- req_common_slots);
-#endif
- continue;
- }
+ if (skip_slot(mslot_class, mask_sel != MASK_TT, rx_window, tx_window, checked_rx))
+ continue;
/* Compute capacity */
capacity = compute_capacity(trx, rx_window, tx_window);
diff --git a/src/mslot_class.c b/src/mslot_class.c
index d403f001..2a482f18 100644
--- a/src/mslot_class.c
+++ b/src/mslot_class.c
@@ -260,3 +260,38 @@ void ts_format(char *buf, uint8_t dl_mask, uint8_t ul_mask)
masked_override_with(buf, ul_mask, 'U');
masked_override_with(buf, ul_mask & dl_mask, 'C');
}
+
+uint16_t mslot_wrap_window(uint16_t win)
+{
+ return (win | win >> 8) & 0xFF;
+}
+
+bool mslot_test_and_set_bit(uint32_t *bits, size_t elem)
+{
+ bool was_set = bits[elem/32] & (1 << (elem % 32));
+ bits[elem/32] |= (1 << (elem % 32));
+
+ return was_set;
+}
+
+/*! Filter out bad slots
+ *
+ * \param[in] mask TS selection mask
+ * \param[in] ul_slots set of UL timeslots
+ * \param[in] dl_slots set of DL timeslots
+ * \param[in] rx_valid_win Mask for valid RX window value
+ * \returns negative error code or RX window on success
+ */
+int16_t mslot_filter_bad(uint8_t mask, uint8_t ul_slots, uint8_t dl_slots, uint16_t rx_valid_win)
+{
+ uint8_t rx_good;
+ uint16_t rx_bad = (uint16_t)(0xFF & ~mask) << ul_slots;
+
+ /* TODO: CHECK this calculation -> separate function for unit testing */
+ rx_bad = (rx_bad | (rx_bad >> 8)) & 0xFF;
+ rx_good = dl_slots & ~rx_bad;
+ if (!rx_good)
+ return -1;
+
+ return rx_good & rx_valid_win;
+}
diff --git a/src/mslot_class.h b/src/mslot_class.h
index 445455f4..045fb317 100644
--- a/src/mslot_class.h
+++ b/src/mslot_class.h
@@ -57,3 +57,6 @@ int8_t find_free_usf(uint8_t usf_map);
int8_t find_free_tfi(uint32_t tfi_map);
void masked_override_with(char *buf, uint8_t mask, char set_char);
void ts_format(char *buf, uint8_t dl_mask, uint8_t ul_mask);
+uint16_t mslot_wrap_window(uint16_t win);
+bool mslot_test_and_set_bit(uint32_t *bits, size_t elem);
+int16_t mslot_filter_bad(uint8_t mask, uint8_t ul_slots, uint8_t dl_slots, uint16_t rx_valid_win);
diff --git a/tests/alloc/MslotTest.cpp b/tests/alloc/MslotTest.cpp
index 1fa28bf5..92f92fae 100644
--- a/tests/alloc/MslotTest.cpp
+++ b/tests/alloc/MslotTest.cpp
@@ -27,6 +27,7 @@
#include <errno.h>
extern "C" {
+ #include "mslot_class.h"
#include <osmocom/core/application.h>
#include <osmocom/core/msgb.h>
#include <osmocom/core/talloc.h>
@@ -137,6 +138,13 @@ static inline void test_multislot_ends(bool seq)
test_all_classes(trx, seq);
}
+static inline void test_window_wrapper()
+{
+ uint16_t i;
+ for (i = 0; i < 256 * 2 + 1; i++)
+ printf("W[%03u] -> %3u %s\n",
+ i, mslot_wrap_window(i), mslot_wrap_window(i) < 256 ? "OK" : "FAIL");
+}
int main(int argc, char **argv)
{
@@ -163,6 +171,8 @@ int main(int argc, char **argv)
test_multislot_ends(true);
test_multislot_ends(false);
+ test_window_wrapper();
+
return EXIT_SUCCESS;
}
diff --git a/tests/alloc/MslotTest.ok b/tests/alloc/MslotTest.ok
index 86526bf7..a47cf57a 100644
--- a/tests/alloc/MslotTest.ok
+++ b/tests/alloc/MslotTest.ok
@@ -1730,3 +1730,516 @@ test_multislot_ends(): accumulative
[ACC] multislot class 44 - UL: .......1 DL: .......1 [0]
[ACC] multislot class 45 - UL: .......1 DL: .......1 [0]
[ACC] multislot class 46 - UL: .......1 DL: .......1 [-22]
+W[000] -> 0 OK
+W[001] -> 1 OK
+W[002] -> 2 OK
+W[003] -> 3 OK
+W[004] -> 4 OK
+W[005] -> 5 OK
+W[006] -> 6 OK
+W[007] -> 7 OK
+W[008] -> 8 OK
+W[009] -> 9 OK
+W[010] -> 10 OK
+W[011] -> 11 OK
+W[012] -> 12 OK
+W[013] -> 13 OK
+W[014] -> 14 OK
+W[015] -> 15 OK
+W[016] -> 16 OK
+W[017] -> 17 OK
+W[018] -> 18 OK
+W[019] -> 19 OK
+W[020] -> 20 OK
+W[021] -> 21 OK
+W[022] -> 22 OK
+W[023] -> 23 OK
+W[024] -> 24 OK
+W[025] -> 25 OK
+W[026] -> 26 OK
+W[027] -> 27 OK
+W[028] -> 28 OK
+W[029] -> 29 OK
+W[030] -> 30 OK
+W[031] -> 31 OK
+W[032] -> 32 OK
+W[033] -> 33 OK
+W[034] -> 34 OK
+W[035] -> 35 OK
+W[036] -> 36 OK
+W[037] -> 37 OK
+W[038] -> 38 OK
+W[039] -> 39 OK
+W[040] -> 40 OK
+W[041] -> 41 OK
+W[042] -> 42 OK
+W[043] -> 43 OK
+W[044] -> 44 OK
+W[045] -> 45 OK
+W[046] -> 46 OK
+W[047] -> 47 OK
+W[048] -> 48 OK
+W[049] -> 49 OK
+W[050] -> 50 OK
+W[051] -> 51 OK
+W[052] -> 52 OK
+W[053] -> 53 OK
+W[054] -> 54 OK
+W[055] -> 55 OK
+W[056] -> 56 OK
+W[057] -> 57 OK
+W[058] -> 58 OK
+W[059] -> 59 OK
+W[060] -> 60 OK
+W[061] -> 61 OK
+W[062] -> 62 OK
+W[063] -> 63 OK
+W[064] -> 64 OK
+W[065] -> 65 OK
+W[066] -> 66 OK
+W[067] -> 67 OK
+W[068] -> 68 OK
+W[069] -> 69 OK
+W[070] -> 70 OK
+W[071] -> 71 OK
+W[072] -> 72 OK
+W[073] -> 73 OK
+W[074] -> 74 OK
+W[075] -> 75 OK
+W[076] -> 76 OK
+W[077] -> 77 OK
+W[078] -> 78 OK
+W[079] -> 79 OK
+W[080] -> 80 OK
+W[081] -> 81 OK
+W[082] -> 82 OK
+W[083] -> 83 OK
+W[084] -> 84 OK
+W[085] -> 85 OK
+W[086] -> 86 OK
+W[087] -> 87 OK
+W[088] -> 88 OK
+W[089] -> 89 OK
+W[090] -> 90 OK
+W[091] -> 91 OK
+W[092] -> 92 OK
+W[093] -> 93 OK
+W[094] -> 94 OK
+W[095] -> 95 OK
+W[096] -> 96 OK
+W[097] -> 97 OK
+W[098] -> 98 OK
+W[099] -> 99 OK
+W[100] -> 100 OK
+W[101] -> 101 OK
+W[102] -> 102 OK
+W[103] -> 103 OK
+W[104] -> 104 OK
+W[105] -> 105 OK
+W[106] -> 106 OK
+W[107] -> 107 OK
+W[108] -> 108 OK
+W[109] -> 109 OK
+W[110] -> 110 OK
+W[111] -> 111 OK
+W[112] -> 112 OK
+W[113] -> 113 OK
+W[114] -> 114 OK
+W[115] -> 115 OK
+W[116] -> 116 OK
+W[117] -> 117 OK
+W[118] -> 118 OK
+W[119] -> 119 OK
+W[120] -> 120 OK
+W[121] -> 121 OK
+W[122] -> 122 OK
+W[123] -> 123 OK
+W[124] -> 124 OK
+W[125] -> 125 OK
+W[126] -> 126 OK
+W[127] -> 127 OK
+W[128] -> 128 OK
+W[129] -> 129 OK
+W[130] -> 130 OK
+W[131] -> 131 OK
+W[132] -> 132 OK
+W[133] -> 133 OK
+W[134] -> 134 OK
+W[135] -> 135 OK
+W[136] -> 136 OK
+W[137] -> 137 OK
+W[138] -> 138 OK
+W[139] -> 139 OK
+W[140] -> 140 OK
+W[141] -> 141 OK
+W[142] -> 142 OK
+W[143] -> 143 OK
+W[144] -> 144 OK
+W[145] -> 145 OK
+W[146] -> 146 OK
+W[147] -> 147 OK
+W[148] -> 148 OK
+W[149] -> 149 OK
+W[150] -> 150 OK
+W[151] -> 151 OK
+W[152] -> 152 OK
+W[153] -> 153 OK
+W[154] -> 154 OK
+W[155] -> 155 OK
+W[156] -> 156 OK
+W[157] -> 157 OK
+W[158] -> 158 OK
+W[159] -> 159 OK
+W[160] -> 160 OK
+W[161] -> 161 OK
+W[162] -> 162 OK
+W[163] -> 163 OK
+W[164] -> 164 OK
+W[165] -> 165 OK
+W[166] -> 166 OK
+W[167] -> 167 OK
+W[168] -> 168 OK
+W[169] -> 169 OK
+W[170] -> 170 OK
+W[171] -> 171 OK
+W[172] -> 172 OK
+W[173] -> 173 OK
+W[174] -> 174 OK
+W[175] -> 175 OK
+W[176] -> 176 OK
+W[177] -> 177 OK
+W[178] -> 178 OK
+W[179] -> 179 OK
+W[180] -> 180 OK
+W[181] -> 181 OK
+W[182] -> 182 OK
+W[183] -> 183 OK
+W[184] -> 184 OK
+W[185] -> 185 OK
+W[186] -> 186 OK
+W[187] -> 187 OK
+W[188] -> 188 OK
+W[189] -> 189 OK
+W[190] -> 190 OK
+W[191] -> 191 OK
+W[192] -> 192 OK
+W[193] -> 193 OK
+W[194] -> 194 OK
+W[195] -> 195 OK
+W[196] -> 196 OK
+W[197] -> 197 OK
+W[198] -> 198 OK
+W[199] -> 199 OK
+W[200] -> 200 OK
+W[201] -> 201 OK
+W[202] -> 202 OK
+W[203] -> 203 OK
+W[204] -> 204 OK
+W[205] -> 205 OK
+W[206] -> 206 OK
+W[207] -> 207 OK
+W[208] -> 208 OK
+W[209] -> 209 OK
+W[210] -> 210 OK
+W[211] -> 211 OK
+W[212] -> 212 OK
+W[213] -> 213 OK
+W[214] -> 214 OK
+W[215] -> 215 OK
+W[216] -> 216 OK
+W[217] -> 217 OK
+W[218] -> 218 OK
+W[219] -> 219 OK
+W[220] -> 220 OK
+W[221] -> 221 OK
+W[222] -> 222 OK
+W[223] -> 223 OK
+W[224] -> 224 OK
+W[225] -> 225 OK
+W[226] -> 226 OK
+W[227] -> 227 OK
+W[228] -> 228 OK
+W[229] -> 229 OK
+W[230] -> 230 OK
+W[231] -> 231 OK
+W[232] -> 232 OK
+W[233] -> 233 OK
+W[234] -> 234 OK
+W[235] -> 235 OK
+W[236] -> 236 OK
+W[237] -> 237 OK
+W[238] -> 238 OK
+W[239] -> 239 OK
+W[240] -> 240 OK
+W[241] -> 241 OK
+W[242] -> 242 OK
+W[243] -> 243 OK
+W[244] -> 244 OK
+W[245] -> 245 OK
+W[246] -> 246 OK
+W[247] -> 247 OK
+W[248] -> 248 OK
+W[249] -> 249 OK
+W[250] -> 250 OK
+W[251] -> 251 OK
+W[252] -> 252 OK
+W[253] -> 253 OK
+W[254] -> 254 OK
+W[255] -> 255 OK
+W[256] -> 1 OK
+W[257] -> 1 OK
+W[258] -> 3 OK
+W[259] -> 3 OK
+W[260] -> 5 OK
+W[261] -> 5 OK
+W[262] -> 7 OK
+W[263] -> 7 OK
+W[264] -> 9 OK
+W[265] -> 9 OK
+W[266] -> 11 OK
+W[267] -> 11 OK
+W[268] -> 13 OK
+W[269] -> 13 OK
+W[270] -> 15 OK
+W[271] -> 15 OK
+W[272] -> 17 OK
+W[273] -> 17 OK
+W[274] -> 19 OK
+W[275] -> 19 OK
+W[276] -> 21 OK
+W[277] -> 21 OK
+W[278] -> 23 OK
+W[279] -> 23 OK
+W[280] -> 25 OK
+W[281] -> 25 OK
+W[282] -> 27 OK
+W[283] -> 27 OK
+W[284] -> 29 OK
+W[285] -> 29 OK
+W[286] -> 31 OK
+W[287] -> 31 OK
+W[288] -> 33 OK
+W[289] -> 33 OK
+W[290] -> 35 OK
+W[291] -> 35 OK
+W[292] -> 37 OK
+W[293] -> 37 OK
+W[294] -> 39 OK
+W[295] -> 39 OK
+W[296] -> 41 OK
+W[297] -> 41 OK
+W[298] -> 43 OK
+W[299] -> 43 OK
+W[300] -> 45 OK
+W[301] -> 45 OK
+W[302] -> 47 OK
+W[303] -> 47 OK
+W[304] -> 49 OK
+W[305] -> 49 OK
+W[306] -> 51 OK
+W[307] -> 51 OK
+W[308] -> 53 OK
+W[309] -> 53 OK
+W[310] -> 55 OK
+W[311] -> 55 OK
+W[312] -> 57 OK
+W[313] -> 57 OK
+W[314] -> 59 OK
+W[315] -> 59 OK
+W[316] -> 61 OK
+W[317] -> 61 OK
+W[318] -> 63 OK
+W[319] -> 63 OK
+W[320] -> 65 OK
+W[321] -> 65 OK
+W[322] -> 67 OK
+W[323] -> 67 OK
+W[324] -> 69 OK
+W[325] -> 69 OK
+W[326] -> 71 OK
+W[327] -> 71 OK
+W[328] -> 73 OK
+W[329] -> 73 OK
+W[330] -> 75 OK
+W[331] -> 75 OK
+W[332] -> 77 OK
+W[333] -> 77 OK
+W[334] -> 79 OK
+W[335] -> 79 OK
+W[336] -> 81 OK
+W[337] -> 81 OK
+W[338] -> 83 OK
+W[339] -> 83 OK
+W[340] -> 85 OK
+W[341] -> 85 OK
+W[342] -> 87 OK
+W[343] -> 87 OK
+W[344] -> 89 OK
+W[345] -> 89 OK
+W[346] -> 91 OK
+W[347] -> 91 OK
+W[348] -> 93 OK
+W[349] -> 93 OK
+W[350] -> 95 OK
+W[351] -> 95 OK
+W[352] -> 97 OK
+W[353] -> 97 OK
+W[354] -> 99 OK
+W[355] -> 99 OK
+W[356] -> 101 OK
+W[357] -> 101 OK
+W[358] -> 103 OK
+W[359] -> 103 OK
+W[360] -> 105 OK
+W[361] -> 105 OK
+W[362] -> 107 OK
+W[363] -> 107 OK
+W[364] -> 109 OK
+W[365] -> 109 OK
+W[366] -> 111 OK
+W[367] -> 111 OK
+W[368] -> 113 OK
+W[369] -> 113 OK
+W[370] -> 115 OK
+W[371] -> 115 OK
+W[372] -> 117 OK
+W[373] -> 117 OK
+W[374] -> 119 OK
+W[375] -> 119 OK
+W[376] -> 121 OK
+W[377] -> 121 OK
+W[378] -> 123 OK
+W[379] -> 123 OK
+W[380] -> 125 OK
+W[381] -> 125 OK
+W[382] -> 127 OK
+W[383] -> 127 OK
+W[384] -> 129 OK
+W[385] -> 129 OK
+W[386] -> 131 OK
+W[387] -> 131 OK
+W[388] -> 133 OK
+W[389] -> 133 OK
+W[390] -> 135 OK
+W[391] -> 135 OK
+W[392] -> 137 OK
+W[393] -> 137 OK
+W[394] -> 139 OK
+W[395] -> 139 OK
+W[396] -> 141 OK
+W[397] -> 141 OK
+W[398] -> 143 OK
+W[399] -> 143 OK
+W[400] -> 145 OK
+W[401] -> 145 OK
+W[402] -> 147 OK
+W[403] -> 147 OK
+W[404] -> 149 OK
+W[405] -> 149 OK
+W[406] -> 151 OK
+W[407] -> 151 OK
+W[408] -> 153 OK
+W[409] -> 153 OK
+W[410] -> 155 OK
+W[411] -> 155 OK
+W[412] -> 157 OK
+W[413] -> 157 OK
+W[414] -> 159 OK
+W[415] -> 159 OK
+W[416] -> 161 OK
+W[417] -> 161 OK
+W[418] -> 163 OK
+W[419] -> 163 OK
+W[420] -> 165 OK
+W[421] -> 165 OK
+W[422] -> 167 OK
+W[423] -> 167 OK
+W[424] -> 169 OK
+W[425] -> 169 OK
+W[426] -> 171 OK
+W[427] -> 171 OK
+W[428] -> 173 OK
+W[429] -> 173 OK
+W[430] -> 175 OK
+W[431] -> 175 OK
+W[432] -> 177 OK
+W[433] -> 177 OK
+W[434] -> 179 OK
+W[435] -> 179 OK
+W[436] -> 181 OK
+W[437] -> 181 OK
+W[438] -> 183 OK
+W[439] -> 183 OK
+W[440] -> 185 OK
+W[441] -> 185 OK
+W[442] -> 187 OK
+W[443] -> 187 OK
+W[444] -> 189 OK
+W[445] -> 189 OK
+W[446] -> 191 OK
+W[447] -> 191 OK
+W[448] -> 193 OK
+W[449] -> 193 OK
+W[450] -> 195 OK
+W[451] -> 195 OK
+W[452] -> 197 OK
+W[453] -> 197 OK
+W[454] -> 199 OK
+W[455] -> 199 OK
+W[456] -> 201 OK
+W[457] -> 201 OK
+W[458] -> 203 OK
+W[459] -> 203 OK
+W[460] -> 205 OK
+W[461] -> 205 OK
+W[462] -> 207 OK
+W[463] -> 207 OK
+W[464] -> 209 OK
+W[465] -> 209 OK
+W[466] -> 211 OK
+W[467] -> 211 OK
+W[468] -> 213 OK
+W[469] -> 213 OK
+W[470] -> 215 OK
+W[471] -> 215 OK
+W[472] -> 217 OK
+W[473] -> 217 OK
+W[474] -> 219 OK
+W[475] -> 219 OK
+W[476] -> 221 OK
+W[477] -> 221 OK
+W[478] -> 223 OK
+W[479] -> 223 OK
+W[480] -> 225 OK
+W[481] -> 225 OK
+W[482] -> 227 OK
+W[483] -> 227 OK
+W[484] -> 229 OK
+W[485] -> 229 OK
+W[486] -> 231 OK
+W[487] -> 231 OK
+W[488] -> 233 OK
+W[489] -> 233 OK
+W[490] -> 235 OK
+W[491] -> 235 OK
+W[492] -> 237 OK
+W[493] -> 237 OK
+W[494] -> 239 OK
+W[495] -> 239 OK
+W[496] -> 241 OK
+W[497] -> 241 OK
+W[498] -> 243 OK
+W[499] -> 243 OK
+W[500] -> 245 OK
+W[501] -> 245 OK
+W[502] -> 247 OK
+W[503] -> 247 OK
+W[504] -> 249 OK
+W[505] -> 249 OK
+W[506] -> 251 OK
+W[507] -> 251 OK
+W[508] -> 253 OK
+W[509] -> 253 OK
+W[510] -> 255 OK
+W[511] -> 255 OK
+W[512] -> 2 OK