1 /**
2 * \file z-dice.c
3 * \brief Represent more complex dice than random_value
4 *
5 * Copyright (c) 2013 Ben Semmler
6 *
7 * This work is free software; you can redistribute it and/or modify it
8 * under the terms of either:
9 *
10 * a) the GNU General Public License as published by the Free Software
11 * Foundation, version 2, or
12 *
13 * b) the "Angband licence":
14 * This software may be copied and distributed for educational, research,
15 * and not for profit purposes provided that this copyright and statement
16 * are included in all such copies. Other copyrights may also apply.
17 */
18
19 #include "z-dice.h"
20 #include "z-virt.h"
21 #include "z-util.h"
22 #include "z-rand.h"
23 #include "z-expression.h"
24
25 typedef struct dice_expression_entry_s {
26 const char *name;
27 const expression_t *expression;
28 } dice_expression_entry_t;
29
30 struct dice_s {
31 int b, x, y, m;
32 bool ex_b, ex_x, ex_y, ex_m;
33 dice_expression_entry_t *expressions;
34 };
35
36 /**
37 * String parser states.
38 */
39 typedef enum dice_state_e {
40 DICE_STATE_START,
41 DICE_STATE_BASE_DIGIT,
42 DICE_STATE_FLUSH_BASE,
43 DICE_STATE_DICE_DIGIT,
44 DICE_STATE_FLUSH_DICE,
45 DICE_STATE_SIDE_DIGIT,
46 DICE_STATE_FLUSH_SIDE,
47 DICE_STATE_BONUS,
48 DICE_STATE_BONUS_DIGIT,
49 DICE_STATE_FLUSH_BONUS,
50 DICE_STATE_VAR,
51 DICE_STATE_VAR_CHAR,
52 DICE_STATE_FLUSH_ALL,
53 DICE_STATE_MAX,
54 } dice_state_t;
55
56 /**
57 * Input types for the parser state table.
58 */
59 typedef enum dice_input_e {
60 DICE_INPUT_AMP,
61 DICE_INPUT_MINUS,
62 DICE_INPUT_BASE,
63 DICE_INPUT_DICE,
64 DICE_INPUT_BONUS,
65 DICE_INPUT_VAR,
66 DICE_INPUT_DIGIT,
67 DICE_INPUT_UPPER,
68 DICE_INPUT_NULL,
69 DICE_INPUT_MAX,
70 } dice_input_t;
71
72 /**
73 * Hard limit on the number of variables/expressions. Shouldn't need more than
74 * the possible values.
75 */
76 #define DICE_MAX_EXPRESSIONS 4
77
78 /**
79 * Max size for a token/number to be parsed. Longer strings will be truncated.
80 */
81 #define DICE_TOKEN_SIZE 16
82
83 /**
84 * Return the appropriate input type based on the given character.
85 */
dice_input_for_char(char c)86 static dice_input_t dice_input_for_char(char c)
87 {
88 /* Catch specific characters before checking bigger char categories. */
89 switch (c) {
90 case '&':
91 return DICE_INPUT_AMP;
92 case '-':
93 return DICE_INPUT_MINUS;
94 case '+':
95 return DICE_INPUT_BASE;
96 case 'd':
97 return DICE_INPUT_DICE;
98 case 'M':
99 case 'm':
100 return DICE_INPUT_BONUS;
101 case '$':
102 return DICE_INPUT_VAR;
103 case '\0':
104 return DICE_INPUT_NULL;
105 default:
106 break;
107 }
108
109 if (isdigit(c))
110 return DICE_INPUT_DIGIT;
111
112 if (isupper(c))
113 return DICE_INPUT_UPPER;
114
115 return DICE_INPUT_MAX;
116 }
117
118 /**
119 * Perform a state transition for the given state and input.
120 *
121 * The state table is contained within this function, using a compact
122 * char-based format.
123 *
124 * \param state is the current state.
125 * \param input is the input type to transition with.
126 * \return The next state for the input, Or DICE_STATE_MAX for an invalid transition.
127 */
dice_parse_state_transition(dice_state_t state,dice_input_t input)128 static dice_state_t dice_parse_state_transition(dice_state_t state,
129 dice_input_t input)
130 {
131 static unsigned char state_table[DICE_STATE_MAX][DICE_INPUT_MAX] = {
132 /* Input: &-+dm$DU0 */
133 /*[DICE_STATE_START] = */ /* A */ ".B.EHKB..",
134 /*[DICE_STATE_BASE_DIGIT] = */ /* B */ "..CE..B.C",
135 /*[DICE_STATE_FLUSH_BASE] = */ /* C */ "...EHKD..",
136 /*[DICE_STATE_DICE_DIGIT] = */ /* D */ "...E..D..",
137 /*[DICE_STATE_FLUSH_DICE] = */ /* E */ ".....KF..",
138 /*[DICE_STATE_SIDE_DIGIT] = */ /* F */ "G...H.F.G",
139 /*[DICE_STATE_FLUSH_SIDE] = */ /* G */ "....H....",
140 /*[DICE_STATE_BONUS] = */ /* H */ ".....KI..",
141 /*[DICE_STATE_BONUS_DIGIT] = */ /* I */ "......I.J",
142 /*[DICE_STATE_FLUSH_BONUS] = */ /* J */ ".........",
143 /*[DICE_STATE_VAR] = */ /* K */ ".......L.",
144 /*[DICE_STATE_VAR_CHAR] = */ /* L */ "G.CEH..LM",
145 /*[DICE_STATE_FLUSH_ALL] = */ /* M */ "........."
146 };
147
148 if (state == DICE_STATE_MAX || input == DICE_INPUT_MAX)
149 return DICE_STATE_MAX;
150
151 if (state_table[state][input] == '.')
152 return DICE_STATE_MAX;
153
154 return state_table[state][input] - 'A';
155 }
156
157 /**
158 * Zero out the internal state of the dice object. This will only deallocate
159 * entries in the expressions table; it will not deallocate the table itself.
160 */
dice_reset(dice_t * dice)161 static void dice_reset(dice_t *dice)
162 {
163 int i;
164
165 dice->b = 0;
166 dice->x = 0;
167 dice->y = 0;
168 dice->m = 0;
169
170 dice->ex_b = false;
171 dice->ex_x = false;
172 dice->ex_y = false;
173 dice->ex_m = false;
174
175 if (dice->expressions == NULL)
176 return;
177
178 for (i = 0; i < DICE_MAX_EXPRESSIONS; i++) {
179 if (dice->expressions[i].name != NULL) {
180 string_free((char *)dice->expressions[i].name);
181 dice->expressions[i].name = NULL;
182 }
183
184 if (dice->expressions[i].expression != NULL) {
185 expression_free((expression_t *)dice->expressions[i].expression);
186 dice->expressions[i].expression = NULL;
187 }
188 }
189 }
190
191 /**
192 * Allocate and initialize a new dice object. Returns NULL if it was unable to
193 * be created.
194 */
dice_new(void)195 dice_t *dice_new(void)
196 {
197 dice_t *dice = mem_zalloc(sizeof(dice_t));
198
199 if (dice == NULL)
200 return NULL;
201
202 dice_reset(dice);
203
204 return dice;
205 }
206
207 /**
208 * Deallocate a dice object.
209 */
dice_free(dice_t * dice)210 void dice_free(dice_t *dice)
211 {
212 if (dice == NULL)
213 return;
214
215 /* Free any variable names and expression objects. */
216 dice_reset(dice);
217
218 if (dice->expressions != NULL) {
219 mem_free(dice->expressions);
220 dice->expressions = NULL;
221 }
222
223 mem_free(dice);
224 }
225
226 /**
227 * Add an entry to the dice object's symbol list.
228 *
229 * \param dice is the object the variable is being added to.
230 * \param name is the name of the variable.
231 * \return The index of the variable name (if added or already found), or -1 for error.
232 */
dice_add_variable(dice_t * dice,const char * name)233 static int dice_add_variable(dice_t *dice, const char *name)
234 {
235 int i;
236
237 if (dice->expressions == NULL) {
238 dice->expressions = mem_zalloc(DICE_MAX_EXPRESSIONS *
239 sizeof(dice_expression_entry_t));
240 }
241
242 for (i = 0; i < DICE_MAX_EXPRESSIONS; i++) {
243 if (dice->expressions[i].name == NULL) {
244 /* Add the variable to an empty slot. */
245 dice->expressions[i].name = string_make(name);
246 return i;
247 }
248 else if (my_stricmp(dice->expressions[i].name, name) == 0) {
249 /* We already have the variable and will use this expression. */
250 return i;
251 }
252 }
253
254 /* No space left for variables. */
255 return -1;
256 }
257
258 /**
259 * Bind an expression to a variable name.
260 *
261 * This function creates a deep copy of the expression that the dice object owns
262 *
263 * \param dice is the object that will use the expression..
264 * \param name is the variable that the expression should be bound to.
265 * \param expression is the expression to bind.
266 * \return The index of the expression or -1 for error.
267 */
dice_bind_expression(dice_t * dice,const char * name,const expression_t * expression)268 int dice_bind_expression(dice_t *dice, const char *name,
269 const expression_t *expression)
270 {
271 int i;
272
273 if (dice->expressions == NULL)
274 return -1;
275
276 for (i = 0; i < DICE_MAX_EXPRESSIONS; i++) {
277 if (dice->expressions[i].name == NULL)
278 continue;
279
280 if (my_stricmp(name, dice->expressions[i].name) == 0) {
281 dice->expressions[i].expression = expression_copy(expression);
282
283 if (dice->expressions[i].expression == NULL)
284 return -1;
285
286 return i;
287 }
288 }
289
290 /* Couldn't find variable name to bind to. */
291 return -1;
292 }
293
294 /**
295 * Parse a formatted string for values and variables to represent a dice roll.
296 *
297 * This function can parse a number of formats in the general style of "1+2d3M4"
298 * (base, dice, sides, and bonus). Varibles (to which expressions can be bound)
299 * can be subsitituted for numeric values by using an all-uppercase name
300 * starting with $.
301 * Spaces are ignored, concatenating the strings on either side of the space
302 * character. Tokens (numbers and variable names) longer than the maximum will
303 * be truncated. The unit test demonstrates the variety of valid strings.
304 *
305 * \param dice is the dice object to parse the string into.
306 * \param string is the string to be parsed.
307 * \return true if parsing was successful, false if not.
308 */
dice_parse_string(dice_t * dice,const char * string)309 bool dice_parse_string(dice_t *dice, const char *string)
310 {
311 char token[DICE_TOKEN_SIZE + 1] = { '\0' };
312 size_t token_end = 0;
313 size_t current = 0;
314 dice_state_t state = 0;
315
316 /* We need to keep track of the last thing we saw, since the parser isn't complex. */
317 enum last_seen_e {
318 DICE_SEEN_NONE,
319 DICE_SEEN_BASE,
320 DICE_SEEN_DICE,
321 DICE_SEEN_SIDE,
322 DICE_SEEN_BONUS,
323 } last_seen = DICE_SEEN_NONE;
324
325 if (dice == NULL || string == NULL)
326 return false;
327
328 /* Reset all internal state, since this object might be reused. */
329 dice_reset(dice);
330
331 /* Note that we are including the string terminator as part of the parse. */
332 for (current = 0; current <= strlen(string); current++) {
333 bool flush;
334 dice_input_t input_type = DICE_INPUT_MAX;
335
336 /* Skip spaces; this will concatenate digits and variable names. */
337 if (isspace(string[current]))
338 continue;
339
340 input_type = dice_input_for_char(string[current]);
341
342 /*
343 * Get the next state, based on the type of input char. If it's a
344 * possible number or varible name, we'll store the character in the
345 * token buffer.
346 */
347 switch (input_type) {
348 case DICE_INPUT_AMP:
349 case DICE_INPUT_BASE:
350 case DICE_INPUT_DICE:
351 case DICE_INPUT_VAR:
352 case DICE_INPUT_NULL:
353 state = dice_parse_state_transition(state, input_type);
354 break;
355
356 case DICE_INPUT_MINUS:
357 case DICE_INPUT_DIGIT:
358 case DICE_INPUT_UPPER:
359 /* Truncate tokens if they are too long to fit. */
360 if (token_end < DICE_TOKEN_SIZE) {
361 token[token_end] = string[current];
362 token_end++;
363 }
364
365 state = dice_parse_state_transition(state, input_type);
366 break;
367
368 default:
369 break;
370 }
371
372 /*
373 * Allow 'M' to be used as the bonus marker and to be used in variable
374 * names.
375 * Ideally, 'm' should be the only marker and this could go away by
376 * adding a case to the switch above for DICE_INPUT_BONUS
377 * (underneath DICE_INPUT_NULL).
378 */
379 if (string[current] == 'M') {
380 if (state == DICE_STATE_VAR || state == DICE_STATE_VAR_CHAR) {
381 if (token_end < DICE_TOKEN_SIZE) {
382 token[token_end] = string[current];
383 token_end++;
384 }
385
386 state = dice_parse_state_transition(state, DICE_INPUT_UPPER);
387 }
388 else
389 state = dice_parse_state_transition(state, DICE_INPUT_BONUS);
390 }
391 else if (string[current] == 'm') {
392 state = dice_parse_state_transition(state, DICE_INPUT_BONUS);
393 }
394
395 /* Illegal transition. */
396 if (state >= DICE_STATE_MAX)
397 return false;
398
399 /*
400 * Default flushing to true, since there are more states that don't
401 * need to be flushed. For some states, we need to do a bit of extra
402 * work, since the parser isn't that complex. A more complex parser
403 * would have more explicit states for variable names.
404 */
405 flush = true;
406
407 switch (state) {
408 case DICE_STATE_FLUSH_BASE:
409 last_seen = DICE_SEEN_BASE;
410 break;
411
412 case DICE_STATE_FLUSH_DICE:
413 last_seen = DICE_SEEN_DICE;
414 /* If we see a 'd' without a number before it, we assume it
415 * to be one die. */
416 if (strlen(token) == 0) {
417 token[0] = '1';
418 token[1] = '\0';
419 }
420 break;
421
422 case DICE_STATE_FLUSH_SIDE:
423 last_seen = DICE_SEEN_SIDE;
424 break;
425
426 case DICE_STATE_FLUSH_BONUS:
427 last_seen = DICE_SEEN_BONUS;
428 break;
429
430 case DICE_STATE_FLUSH_ALL:
431 /* Flushing all means that we are flushing whatever comes after
432 * it was that we last saw. */
433 if (last_seen < DICE_SEEN_BONUS)
434 last_seen++;
435 break;
436
437 case DICE_STATE_BONUS:
438 /* The bonus state is weird, so if we last saw dice, we're now
439 * seeing sides. */
440 if (last_seen == DICE_SEEN_DICE)
441 last_seen = DICE_SEEN_SIDE;
442 else
443 last_seen = DICE_SEEN_BONUS;
444 break;
445
446 default:
447 /* We're in a state that shouldn't flush anything. */
448 flush = false;
449 break;
450 }
451
452 /*
453 * If we have a token that we need to flush, put it where it needs to
454 * go in the dice object. If the token is an uppercase letter, it's
455 * a variable and needs to go in the expression table. Otherwise, we
456 * try to parse it as a number, where it is set directly as a value.
457 */
458 if (flush && strlen(token) > 0) {
459 int value = 0;
460 bool is_variable = false;
461
462 if (isupper(token[0])) {
463 value = dice_add_variable(dice, token);
464 is_variable = true;
465 }
466 else {
467 value = (int)strtol(token, NULL, 0);
468 is_variable = false;
469 }
470
471 switch (last_seen) {
472 case DICE_SEEN_BASE:
473 dice->b = value;
474 dice->ex_b = is_variable;
475 break;
476 case DICE_SEEN_DICE:
477 dice->x = value;
478 dice->ex_x = is_variable;
479 break;
480 case DICE_SEEN_SIDE:
481 dice->y = value;
482 dice->ex_y = is_variable;
483 break;
484 case DICE_SEEN_BONUS:
485 dice->m = value;
486 dice->ex_m = is_variable;
487 break;
488 default:
489 break;
490 }
491
492 memset(token, 0, DICE_TOKEN_SIZE + 1);
493 token_end = 0;
494 }
495 }
496
497 return true;
498 }
499
500 /**
501 * Extract a random_value by evaluating any bound expressions.
502 *
503 * \param dice is the object to get the random_value from.
504 * \param v is the random_value to place the values into.
505 */
dice_random_value(dice_t * dice,random_value * v)506 void dice_random_value(dice_t *dice, random_value *v)
507 {
508 if (v == NULL)
509 return;
510
511 if (dice->ex_b) {
512 if (dice->expressions != NULL && dice->expressions[dice->b].expression != NULL)
513 v->base = expression_evaluate(dice->expressions[dice->b].expression);
514 else
515 v->base = 0;
516 }
517 else
518 v->base = dice->b;
519
520 if (dice->ex_x) {
521 if (dice->expressions != NULL && dice->expressions[dice->x].expression != NULL)
522 v->dice = expression_evaluate(dice->expressions[dice->x].expression);
523 else
524 v->dice = 0;
525 }
526 else
527 v->dice = dice->x;
528
529 if (dice->ex_y) {
530 if (dice->expressions != NULL && dice->expressions[dice->y].expression != NULL)
531 v->sides = expression_evaluate(dice->expressions[dice->y].expression);
532 else
533 v->sides = 0;
534 }
535 else
536 v->sides = dice->y;
537
538 if (dice->ex_m) {
539 if (dice->expressions != NULL && dice->expressions[dice->m].expression != NULL)
540 v->m_bonus = expression_evaluate(dice->expressions[dice->m].expression);
541 else
542 v->m_bonus = 0;
543 }
544 else
545 v->m_bonus = dice->m;
546 }
547
548 /**
549 * Fully evaluates the dice object, using randcalc(). The random_value used is
550 * returned if desired.
551 *
552 * \param dice is the dice object to evaluate.
553 * \param level is the level value that is passed to randcalc().
554 * \param aspect is the aspect that is passed to randcalc().
555 * \param v is a pointer used to return the random_value used.
556 */
dice_evaluate(dice_t * dice,int level,aspect aspect,random_value * v)557 int dice_evaluate(dice_t *dice, int level, aspect aspect, random_value *v)
558 {
559 random_value rv;
560 dice_random_value(dice, &rv);
561
562 if (v != NULL) {
563 v->base = rv.base;
564 v->dice = rv.dice;
565 v->sides = rv.sides;
566 v->m_bonus = rv.m_bonus;
567 }
568
569 return randcalc(rv, level, aspect);
570 }
571
572 /**
573 * Evaluates the dice object, using damroll() (base + XdY). The random_value
574 * used is returned if desired.
575 *
576 * \param dice is the dice object to evaluate.
577 * \param v is a pointer used to return the random_value used.
578 */
dice_roll(dice_t * dice,random_value * v)579 int dice_roll(dice_t *dice, random_value *v)
580 {
581 random_value rv;
582 dice_random_value(dice, &rv);
583
584 if (v != NULL) {
585 v->base = rv.base;
586 v->dice = rv.dice;
587 v->sides = rv.sides;
588 v->m_bonus = rv.m_bonus;
589 }
590
591 return rv.base + damroll(rv.dice, rv.sides);
592 }
593
594 /**
595 * Test the dice object against the given values.
596 */
dice_test_values(dice_t * dice,int base,int dice_count,int sides,int bonus)597 bool dice_test_values(dice_t *dice, int base, int dice_count, int sides,
598 int bonus)
599 {
600 bool success = true;
601 success &= dice->b == base;
602 success &= dice->x == dice_count;
603 success &= dice->y == sides;
604 success &= dice->m == bonus;
605 return success;
606 }
607
608 /**
609 * Check that the dice object has the given variables for the component.
610 */
dice_test_variables(dice_t * dice,const char * base,const char * dice_name,const char * sides,const char * bonus)611 bool dice_test_variables(dice_t *dice, const char *base, const char *dice_name,
612 const char *sides, const char *bonus)
613 {
614 bool success = true;
615
616 if (dice->expressions == NULL)
617 return false;
618
619 if (base == NULL)
620 success &= !dice->ex_b;
621 else
622 success &= (dice->ex_b && dice->b >= 0 && my_stricmp(dice->expressions[dice->b].name, base) == 0);
623
624 if (dice_name == NULL)
625 success &= !dice->ex_x;
626 else
627 success &= (dice->ex_x && dice->x >= 0 && my_stricmp(dice->expressions[dice->x].name, dice_name) == 0);
628
629 if (sides == NULL)
630 success &= !dice->ex_y;
631 else
632 success &= (dice->ex_y && dice->y >= 0 && my_stricmp(dice->expressions[dice->y].name, sides) == 0);
633
634 if (bonus == NULL)
635 success &= !dice->ex_m;
636 else
637 success &= (dice->ex_m && dice->m >= 0 && my_stricmp(dice->expressions[dice->m].name, bonus) == 0);
638
639 return success;
640 }
641