aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMax <msuraev@sysmocom.de>2018-02-05 16:15:30 +0100
committerNeels Hofmeyr <neels@hofmeyr.de>2018-02-27 22:27:53 +0100
commitdeeb68bebabb7a7fc749592145abeebb0ca7d3ad (patch)
treef595b62639f632c76e54b74a87dbeeba31bd443d
parent321bf390d0ae41d2bce36433c468e410ae6fc840 (diff)
Simplify TS alloc: move slot check into functionsneels/master
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 4cc9539..835c199 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 d403f00..2a482f1 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 445455f..045fb31 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 1fa28bf..92f92fa 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 86526bf..a47cf57 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