| summaryrefslogtreecommitdiff |
diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/core/CMakeLists.txt | 2 | ||||
| -rw-r--r-- | src/core/create_sentences.c | 706 | ||||
| -rw-r--r-- | src/core/create_sequence.c | 654 | ||||
| -rw-r--r-- | src/core/index.h | 8 | ||||
| -rw-r--r-- | src/core/index_types.h | 8 | ||||
| -rw-r--r-- | src/pervasive.h | 2 |
6 files changed, 671 insertions, 709 deletions
diff --git a/src/core/CMakeLists.txt b/src/core/CMakeLists.txt index a8ec17e..af5ca65 100644 --- a/src/core/CMakeLists.txt +++ b/src/core/CMakeLists.txt @@ -3,7 +3,7 @@ set( ${CMAKE_CURRENT_SOURCE_DIR}/main.c ${CMAKE_CURRENT_SOURCE_DIR}/knowledge.c ${CMAKE_CURRENT_SOURCE_DIR}/assimilate.c - ${CMAKE_CURRENT_SOURCE_DIR}/create_sentences.c + ${CMAKE_CURRENT_SOURCE_DIR}/create_sequence.c ${CMAKE_CURRENT_SOURCE_DIR}/sequence.c ) diff --git a/src/core/create_sentences.c b/src/core/create_sentences.c deleted file mode 100644 index 93444a7..0000000 --- a/src/core/create_sentences.c +++ /dev/null @@ -1,706 +0,0 @@ -#include <stdlib.h> -#include <stdio.h> -#include <string.h> -#include <stdint.h> /* defines SIZE_MAX */ - -#include "../io/error.h" - -#include "knowledge.h" - -/** Functions to create sentences using a ZoO_knowledge structure *************/ - -/* - * Returns the index of a element in {links} chosen randomly according - * to the distribution in {links_occurrences}. - * Pre: - * (!= occurrences 0). - * (== (length links_occurrences) (length links)). - * (== (sum links_occurrences) occurrences). - * (can_store ZoO_index (length links)). - */ -static ZoO_index pick_index -( - ZoO_index const occurrences, - const ZoO_index links_occurrences [const restrict static 1] -) -{ - ZoO_index result, accumulator, random_number; - - result = 0; - - /* - * Safe: - * (> (length links_occurrences) 0). - */ - accumulator = links_occurrences[0]; - - random_number = (((ZoO_index) rand()) % occurrences); - - while (accumulator < random_number) - { - /* - * Safe: - * (-> - * (and - * (== accumulator (sum links_occurrences[0:result])) - * (< accumulator random_number) - * (< random_number occurrences) - * (== occurrences (sum links_occurrences)) - * (can_store ZoO_index (length links)) - * (== (length links_occurrences) (length links)) - * ) - * (and - * (< result' (length links_occurrences)) - * (can_store ZoO_index result') - * (=< accumulator' occurrences) - * ) - * ) - */ - result += 1; - accumulator += links_occurrences[result]; - } - - /* Safe: (< result (length links)) */ - return result; -} - -static unsigned char * extend_left -( - struct ZoO_knowledge k [const restrict static 1], - ZoO_index sequence [const restrict static ZoO_MARKOV_ORDER], - ZoO_char current_sentence [static 1], - size_t sentence_size [const restrict static 1], - ZoO_index credits [const static 1] -) -{ - size_t addition_size; - struct ZoO_knowledge_word * w; - ZoO_char * next_sentence; - ZoO_index j; - - /* prevents current_sentence [restrict] */ - next_sentence = current_sentence; - - for (;;) - { - if (*credits == 0) - { - return current_sentence; - } - - *credits -= 1; - - w = (k->words + sequence[ZoO_MARKOV_ORDER - 1]); - - switch (w->special) - { - case ZoO_WORD_HAS_NO_EFFECT: - /* FIXME: not overflow-safe. */ - /* word also contains an '\0', which we will replace by a ' ' */ - addition_size = w->word_size; - break; - - case ZoO_WORD_ENDS_SENTENCE: - ZoO_S_WARNING("END OF LINE should not be prefixable."); - return current_sentence; - - case ZoO_WORD_STARTS_SENTENCE: - return current_sentence; - - case ZoO_WORD_REMOVES_LEFT_SPACE: - case ZoO_WORD_REMOVES_RIGHT_SPACE: - /* word also contains an '\0', which we will remove. */ - addition_size = w->word_size - 1; - break; - } - - if (*sentence_size > (SIZE_MAX - addition_size)) - { - ZoO_S_WARNING - ( - "Sentence construction aborted to avoid size_t overflow." - ); - - return current_sentence; - } - - next_sentence = - (ZoO_char *) calloc - ( - /* overflow-safe */ - (*sentence_size + addition_size), - sizeof(ZoO_char) - ); - - if (next_sentence == (ZoO_char *) NULL) - { - ZoO_S_ERROR("Could not allocate memory to store new sentence."); - - return current_sentence; - } - - /* overflow-safe */ - *sentence_size = (*sentence_size + addition_size); - - switch (w->special) - { - case ZoO_WORD_HAS_NO_EFFECT: - snprintf - ( - next_sentence, - *sentence_size, - " " ZoO_CHAR_STRING_SYMBOL ZoO_CHAR_STRING_SYMBOL, - w->word, - current_sentence - ); - break; - - case ZoO_WORD_REMOVES_LEFT_SPACE: - snprintf - ( - next_sentence, - *sentence_size, - ZoO_CHAR_STRING_SYMBOL ZoO_CHAR_STRING_SYMBOL, - w->word, - current_sentence - ); - break; - - case ZoO_WORD_REMOVES_RIGHT_SPACE: - snprintf - ( - next_sentence, - *sentence_size, - ZoO_CHAR_STRING_SYMBOL ZoO_CHAR_STRING_SYMBOL, - w->word, - /* Safe: strlen(current_sentence) >= 2 */ - (current_sentence + 1) - ); - break; - - default: - /* TODO: PROGRAM LOGIC ERROR */ - break; - } - - free((void *) current_sentence); - - /* prevents current_sentence [const] */ - current_sentence = next_sentence; - - memmove - ( - (void *) (sequence + 1), - (const void *) sequence, - /* Accepts 0. */ - (sizeof(ZoO_index) * (ZoO_MARKOV_ORDER - 1)) - ); - - if - ( - ZoO_knowledge_find_link - ( - w->backward_links_count, - w->backward_links, - (sequence + 1), - &j - ) - < 0 - ) - { - ZoO_S_ERROR("Unexpectedly, no backtracking link was found."); - - break; - } - - sequence[0] = - w->backward_links[j].targets - [ - pick_index - ( - w->backward_links[j].occurrences, - w->backward_links[j].targets_occurrences - ) - ]; - - /* prevents current_sentence [const] */ - current_sentence = next_sentence; - } -} - -static unsigned char * extend_right -( - struct ZoO_knowledge k [const restrict static 1], - ZoO_index sequence [const restrict static ZoO_MARKOV_ORDER], - ZoO_char current_sentence [static 1], - size_t sentence_size [const restrict static 1], - ZoO_index credits [const static 1] -) -{ - size_t addition_size; - struct ZoO_knowledge_word * w; - ZoO_char * next_sentence; - ZoO_index j; - - /* prevents current_sentence [restrict] */ - next_sentence = current_sentence; - - for (;;) - { - if (*credits == 0) - { - return current_sentence; - } - - *credits -= 1; - - w = (k->words + sequence[0]); - - switch (w->special) - { - case ZoO_WORD_HAS_NO_EFFECT: - /* FIXME: Assumed to be overflow-safe. */ - /* word also contains an '\0', which we will replace by a ' '. */ - addition_size = w->word_size; - break; - - case ZoO_WORD_ENDS_SENTENCE: - return current_sentence; - - case ZoO_WORD_STARTS_SENTENCE: - ZoO_S_WARNING("START OF LINE should not be suffixable."); - return current_sentence; - - case ZoO_WORD_REMOVES_LEFT_SPACE: - case ZoO_WORD_REMOVES_RIGHT_SPACE: - /* word also contains an '\0', which we will remove. */ - addition_size = w->word_size - 1; - break; - } - - if (*sentence_size > (SIZE_MAX - addition_size)) - { - ZoO_S_WARNING - ( - "Sentence construction aborted to avoid size_t overflow." - ); - - return current_sentence; - } - - next_sentence = - (ZoO_char *) calloc - ( - /* overflow-safe */ - (*sentence_size + addition_size), - sizeof(ZoO_char) - ); - - if (next_sentence == (ZoO_char *) NULL) - { - ZoO_S_ERROR("Could not allocate memory to store new sentence."); - - return current_sentence; - } - - /* overflow-safe */ - *sentence_size = (*sentence_size + addition_size); - - switch (w->special) - { - case ZoO_WORD_REMOVES_LEFT_SPACE: - current_sentence[*sentence_size - addition_size - 2] = '\0'; - - case ZoO_WORD_HAS_NO_EFFECT: - snprintf - ( - next_sentence, - *sentence_size, - ZoO_CHAR_STRING_SYMBOL ZoO_CHAR_STRING_SYMBOL " ", - current_sentence, - w->word - ); - break; - - case ZoO_WORD_REMOVES_RIGHT_SPACE: - snprintf - ( - next_sentence, - *sentence_size, - ZoO_CHAR_STRING_SYMBOL ZoO_CHAR_STRING_SYMBOL, - current_sentence, - w->word - ); - break; - - default: - /* TODO: PROGRAM LOGIC ERROR */ - break; - } - - free((void *) current_sentence); - - /* prevents current_sentence [const] */ - current_sentence = next_sentence; - - memmove - ( - (void *) sequence, - (const void *) (sequence + 1), - /* Accepts 0. */ - (sizeof(ZoO_index) * (ZoO_MARKOV_ORDER - 1)) - ); - - if - ( - ZoO_knowledge_find_link - ( - w->forward_links_count, - w->forward_links, - sequence, - &j - ) - < 0 - ) - { - ZoO_S_ERROR("Unexpectedly, no forward link was found."); - - break; - } - - sequence[ZoO_MARKOV_ORDER - 1] = - w->forward_links[j].targets - [ - pick_index - ( - w->forward_links[j].occurrences, - w->forward_links[j].targets_occurrences - ) - ]; - } -} - -static ZoO_index select_first_word -( - struct ZoO_knowledge k [const static 1], - const struct ZoO_strings string [const], - ZoO_index const aliases_count, - const char * restrict aliases [const restrict static aliases_count] -) -{ - ZoO_index i, j, word_id, word_min_score, word_min_id; - ZoO_index word_found; - - if (string == (struct ZoO_strings *) NULL) - { - return word_min_id = (rand() % k->words_count); - } - - word_found = 0; - - for (i = 0; i < string->words_count; ++i) - { - for (j = 0; j < aliases_count; ++j) - { - if (ZoO_IS_PREFIX(aliases[j], string->words[i])) - { - goto NEXT_WORD; - } - } - - /* prevents k [restrict] */ - if (ZoO_knowledge_find(k, string->words[i], &word_min_id) == 0) - { - word_found = 1; - word_min_score = k->words[word_min_id].occurrences; - - break; - } - - NEXT_WORD:; - } - - if (word_found == 0) - { - return word_min_id = (rand() % k->words_count); - } - - for (; i < string->words_count; ++i) - { - for (j = 0; j < aliases_count; ++j) - { - if (ZoO_IS_PREFIX(aliases[j], string->words[i])) - { - goto NEXT_WORD_BIS; - } - } - - if - ( - (ZoO_knowledge_find(k, string->words[i], &word_id) == 0) - && (k->words[word_id].occurrences < word_min_score) - ) - { - word_min_score = k->words[word_id].occurrences; - word_min_id = word_id; - } - - NEXT_WORD_BIS:; - } - - return word_min_id; -} - -static void init_sequence -( - struct ZoO_knowledge k [const static 1], - const struct ZoO_strings string [const], - ZoO_index const aliases_count, - const char * restrict aliases [const restrict static aliases_count], - ZoO_index sequence [const static (ZoO_MARKOV_ORDER * 2) + 1] -) -{ - ZoO_index i, j, accumulator, random_number; - struct ZoO_knowledge_word * fiw; - - sequence[ZoO_MARKOV_ORDER] = - select_first_word( - k, - string, - aliases_count, - aliases - ); - - fiw = (k->words + sequence[ZoO_MARKOV_ORDER]); - - for (i = 0; i < ZoO_MARKOV_ORDER; ++i) - { - sequence[ZoO_MARKOV_ORDER - i - 1] = ZoO_WORD_START_OF_LINE; - sequence[ZoO_MARKOV_ORDER + i + 1] = ZoO_WORD_END_OF_LINE; - } - - if (fiw->forward_links_count == 0) - { - ZoO_S_FATAL("First word has no forward links."); - - return; - } - - /* Chooses a likely forward link for the pillar. */ - i = 0; - accumulator = fiw->forward_links[0].occurrences; - - random_number = (((ZoO_index) rand()) % fiw->occurrences); - - while (accumulator < random_number) - { - accumulator += fiw->forward_links[i].occurrences; - i += 1; - } - -/* i = (((ZoO_index) rand()) % fiw->forward_links_count); */ - - /* Copies the forward link data into the sequence. */ - /* This adds (ZoO_MARKOV_ORDER - 1) words, as the ZoO_MARKOV_ORDERth word */ - /* is chosen aftewards. */ - memcpy - ( - (void *) (sequence + ZoO_MARKOV_ORDER + 1), - fiw->forward_links[i].sequence, - sizeof(ZoO_index) * (ZoO_MARKOV_ORDER - 1) - ); - - /* selects the last word */ - sequence[ZoO_MARKOV_ORDER * 2] = - fiw->forward_links[i].targets - [ - pick_index - ( - fiw->forward_links[i].occurrences, - fiw->forward_links[i].targets_occurrences - ) - ]; - - /* FIXME: Not clear enough. */ - /* Now that we have the right side of the sequence, we are going to */ - /* build the left one, one word at a time. */ - for (i = 0; i < ZoO_MARKOV_ORDER; ++i) - { - /* temporary pillar (starts on the right side, minus one so we don't */ - fiw = (k->words + sequence[(ZoO_MARKOV_ORDER * 2) - i - 1]); - - if - ( - /* finds the backward link corresponding to the words left of the */ - /* temporary pillar. */ - ZoO_knowledge_find_link - ( - fiw->backward_links_count, - fiw->backward_links, - sequence + (ZoO_MARKOV_ORDER - i), - &j - ) - < 0 - ) - { - ZoO_ERROR - ( - "Unexpectedly, no back link was found at i=%u, expected to find" - "a backlink with %s, from %s.", - i, - k->words[sequence[(ZoO_MARKOV_ORDER - i)]].word, - fiw->word - ); - ZoO_S_ERROR("Sequence was:"); - - for (j = 0; j <= (ZoO_MARKOV_ORDER * 2); ++j) - { - ZoO_ERROR("[%u] %s", j, k->words[sequence[j]].word); - } - - break; - } - - sequence[ZoO_MARKOV_ORDER - i - 1] = - fiw->backward_links[j].targets - [ - pick_index - ( - fiw->backward_links[j].occurrences, - fiw->backward_links[j].targets_occurrences - ) - ]; - } -} - -int ZoO_knowledge_extend -( - struct ZoO_knowledge k [const static 1], - const struct ZoO_strings string [const], - ZoO_index const aliases_count, - const char * restrict aliases [const restrict static aliases_count], - ZoO_char * result [const static 1] -) -{ - int word_found; - size_t sentence_size; - ZoO_index sequence[(ZoO_MARKOV_ORDER * 2) + 1]; - ZoO_index first_word, credits; - - credits = ZoO_MAX_REPLY_WORDS; - - init_sequence(k, string, aliases_count, aliases, sequence); - - first_word = sequence[ZoO_MARKOV_ORDER]; - - /* 3: 2 spaces + '\0' */ - /* FIXME: not overflow-safe */ - switch (k->words[first_word].special) - { - case ZoO_WORD_REMOVES_LEFT_SPACE: - case ZoO_WORD_REMOVES_RIGHT_SPACE: - /* word + ' ' + '\0' */ - sentence_size = (strlen(k->words[first_word].word) + 2); - break; - - case ZoO_WORD_HAS_NO_EFFECT: - /* word + ' ' * 2 + '\0' */ - sentence_size = (strlen(k->words[first_word].word) + 3); - break; - - default: - ZoO_WARNING - ( - "'%s' was unexpectedly selected as pillar.", - k->words[first_word].word - ); - /* word + '[' + ']' + ' ' * 2 + '\0' */ - sentence_size = (strlen(k->words[first_word].word) + 5); - break; - } - - *result = (ZoO_char *) calloc(sentence_size, sizeof(ZoO_char)); - - if (*result == (ZoO_char *) NULL) - { - ZoO_S_ERROR("Could not allocate memory to start sentence."); - - return -2; - } - - switch (k->words[first_word].special) - { - case ZoO_WORD_REMOVES_LEFT_SPACE: - snprintf - ( - *result, - sentence_size, - ZoO_CHAR_STRING_SYMBOL " ", - k->words[first_word].word - ); - break; - - case ZoO_WORD_REMOVES_RIGHT_SPACE: - snprintf - ( - *result, - sentence_size, - " " ZoO_CHAR_STRING_SYMBOL, - k->words[first_word].word - ); - break; - - case ZoO_WORD_HAS_NO_EFFECT: - snprintf - ( - *result, - sentence_size, - " " ZoO_CHAR_STRING_SYMBOL " ", - k->words[first_word].word - ); - break; - - default: - snprintf - ( - *result, - sentence_size, - " [" ZoO_CHAR_STRING_SYMBOL "] ", - k->words[first_word].word - ); - break; - } - - /* prevents result [restrict] */ - *result = - extend_right - ( - k, - (sequence + ZoO_MARKOV_ORDER + 1), - *result, - &sentence_size, - &credits - ); - - if (*result == (ZoO_char *) NULL) - { - return -2; - } - - *result = - extend_left - ( - k, - sequence, - *result, - &sentence_size, - &credits - ); - - if (*result == (ZoO_char *) NULL) - { - return -2; - } - - return 0; -} diff --git a/src/core/create_sequence.c b/src/core/create_sequence.c new file mode 100644 index 0000000..a7b96f9 --- /dev/null +++ b/src/core/create_sequence.c @@ -0,0 +1,654 @@ +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <stdint.h> /* defines SIZE_MAX */ + +#include "../io/error.h" + +#include "../core/index.h" + +#include "knowledge.h" + +/* + * Returns a randomly chosen index pointing to a element in {weights}. + * The values of {weights} are used as weights to guide the choice. + * Returns: + * Value in [0, (length weights)[. + * Pre: + * (> weights_sum 0). + * (= (sum weights) weights_sum). + */ +static ZoO_index weighted_random_pick +( + const ZoO_index weights [const restrict static 1], + const ZoO_index weights_sum +) +{ + ZoO_index result, accumulator, random_number; + + accumulator = 0; + + /* Safe: Included in [0, weights_sum]. */ + random_number = ZoO_index_random_up_to(weights_sum); + + for (result = 0; accumulator < random_number; ++result) + { + /* Safe: (= (sum weights) weights_sum) */ + accumulator += weights[result]; + } + + return result; +} + +/* + * FIXME: This does not belong here. + * Calculates the size the sentence will have upon addition of the word, taking + * into account {effect}. + * Returns: + * 0 on success. + * -1 iff adding the word would overflow {sentence_size}. + * Post: + * (initialized new_size) + */ +static int get_new_size +( + const size_t word_size, + const size_t sentence_size, + const enum ZoO_knowledge_special_effect effect, + size_t new_size [const restrict static 1] +) +{ + size_t added_size; + + switch (effect) + { + case ZoO_WORD_HAS_NO_EFFECT: + /* word also contains an '\0', which we will replace by a ' ' */ + added_size = word_size; + break; + + case ZoO_WORD_ENDS_SENTENCE: + case ZoO_WORD_STARTS_SENTENCE: + added_size = 0; + break; + + case ZoO_WORD_REMOVES_LEFT_SPACE: + case ZoO_WORD_REMOVES_RIGHT_SPACE: + /* word also contains an '\0', which we will remove. */ + added_size = (word_size - 1); + break; + } + + if ((SIZE_MAX - word_size) > sentence_size) + { + /* New size Would overflow. */ + *new_size = sentence_size; + + return -1; + } + + /* Safe: (=< SIZE_MAX (+ sentence_size added_size)) */ + *new_size = (sentence_size + added_size); + + return 0; +} + +/******************************************************************************/ +/** ADDING ELEMENTS TO THE LEFT ***********************************************/ +/******************************************************************************/ + +/* + * Adds an id to the left of the sequence. + * This requires the reallocation of {sequence}. The freeing of the previous + * memory space is handled. If an error happened, {sequence} remain untouched. + * Returns: + * 0 on success. + * -1 iff adding the word would cause an overflow. + * -2 iff memory allocation was unsuccessful. + * Post: + * (initialized {sequence}) + * (initialized {*sequence}) + */ +static int left_append +( + const ZoO_index word_id, + ZoO_index * sequence [const restrict], + const size_t sequence_size +) +{ + ZoO_index * new_sequence; + + if ((SIZE_MAX - sizeof(ZoO_index)) > sequence_size) + { + ZoO_S_ERROR + ( + "Left side append aborted, as the new sequence's size would overflow." + ); + + return -1; + } + + new_sequence = (ZoO_index *) malloc(sizeof(ZoO_index) + sequence_size); + + if (new_sequence == (ZoO_index *) NULL) + { + ZoO_S_ERROR + ( + "Left side append aborted, as memory for the new sequence could not be" + " allocated." + ); + + return -2; + } + + if (sequence_size > 0) + { + memcpy + ( + (void *) (new_sequence + 1), + (const void *) sequence, + sequence_size + ); + + free((void *) sequence); + } + + new_sequence[0] = word_id; + + *sequence = new_sequence; + + return 0; +} + +/* + * Adds an id to the left of the sequence, according to what is known as likely + * to fit there. + * This requires the reallocation of {sequence}. The freeing of the previous + * memory space is handled. If an error happened, {sequence} remain untouched. + * Returns: + * 0 on success. + * -1 iff nothing fitting was found. + * -2 iff the addition of that id failed. + * Pre: + * (initialized {sequence}) + * (initialized {*sequence[0..(MARKOV_ORDER - 1)]}) + */ +static int extend_left +( + ZoO_index * sequence [const restrict static 1], + const size_t sequence_size, + const struct ZoO_knowledge k [const restrict static 1] +) +{ + const ZoO_index * restrict preceding_words; + const ZoO_index * restrict preceding_words_weights; + ZoO_index preceding_words_weights_sum; + + if + ( + ZoO_knowledge_get_preceding_words + ( + k, + *sequence, + &preceding_words, + &preceding_words_weights, + &preceding_words_weights_sum + ) < 0 + ) + { + return -1; + } + + /* preceding_words_weights_sum > 0 */ + + if + ( + left_append + ( + weighted_random_pick + ( + preceding_words_weights, + preceding_words_weights_sum + ), + sequence, + sequence_size + ) < 0 + ) + { + return -3; + } + + return 0; +} + +static int complete_left_part_of_sequence +( + ZoO_index * sequence [restrict static 1], + size_t sequence_size [const restrict static 1], + ZoO_index credits [const restrict], + const struct ZoO_knowledge k [const restrict static 1] +) +{ + for (;;) + { + if ((credits == (ZoO_index *) NULL) || (*credits > 0)) + { + if (extend_left(sequence, *sequence_size, k) < 0) + { + /* We are sure *sequence[0] is defined. */ + if (*sequence[0] == ZoO_START_OF_SEQUENCE_ID) + { + /* + * We failed to add a word, but it was because none should have + * been added. + */ + return 0; + } + else + { + return -1; + } + } + } + else + { + /* No more credits available, the sequence will have to start here. */ + *sequence[0] = ZoO_START_OF_SEQUENCE_ID; + + return 0; + } + + /* + * Safe: if it was going to overflow, extend_left would have returned a + * negative value, making this statement unreachable. + */ + *sequence_size = (*sequence_size + sizeof(ZoO_index)); + + if (credits != (ZoO_index *) NULL) + { + *credits -= 1; + } + + /* We are sure *sequence[0] is defined. */ + switch (*sequence[0]) + { + case ZoO_END_OF_SEQUENCE_ID: + ZoO_S_WARNING + ( + "END OF LINE was added at the left part of an sequence." + ); + + *sequence[0] = ZoO_START_OF_SEQUENCE_ID; + return 0; + + case ZoO_START_OF_SEQUENCE_ID: + return 0; + + default: + break; + } + } +} + +/******************************************************************************/ +/** ADDING ELEMENTS TO THE RIGHT **********************************************/ +/******************************************************************************/ + +/* + * Adds an id to the right of the sequence. + * This requires the reallocation of {sequence}. The freeing of the previous + * memory space is handled. If an error happened, {sequence} remain untouched. + * Returns: + * 0 on success. + * -1 iff adding the word would cause an overflow. + * -2 iff memory allocation was unsuccessful. + * Post: + * (initialized {sequence}) + * (initialized {*sequence}) + */ +static int right_append +( + ZoO_index * sequence [const restrict], + const ZoO_index word_id, + const size_t sequence_size, + const ZoO_index sequence_length +) +{ + ZoO_index * new_sequence; + + if ((SIZE_MAX - sizeof(ZoO_index)) > sequence_size) + { + ZoO_S_ERROR + ( + "Right side append aborted, as the new sequence's size would overflow." + ); + + return -1; + } + + new_sequence = + (ZoO_index *) realloc + ( + sequence, + (sequence_size + sizeof(ZoO_index)) + ); + + if (new_sequence == (ZoO_index *) NULL) + { + ZoO_S_ERROR + ( + "Right side append aborted, as memory for the new sequence could not " + "be allocated." + ); + + return -2; + } + + new_sequence[sequence_length] = word_id; + + *sequence = new_sequence; + + return 0; +} + +static int extend_right +( + ZoO_index * sequence [const restrict static 1], + const size_t sequence_size, + const ZoO_index sequence_length, + const struct ZoO_knowledge k [const restrict static 1] +) +{ + const ZoO_index * restrict following_words; + const ZoO_index * restrict following_words_weights; + + ZoO_index following_words_weights_sum; + + if + ( + ZoO_knowledge_get_following_words + ( + k, + *sequence, + sequence_length, + &following_words, + &following_words_weights, + &following_words_weights_sum + ) < 0 + ) + { + return -1; + } + + /* following_words_weights_sum > 0 */ + + if + ( + right_append + ( + sequence, + weighted_random_pick + ( + following_words_weights, + following_words_weights_sum + ), + sequence_size, + sequence_length + ) < 0 + ) + { + return -3; + } + + return 0; +} + +static int complete_right_part_of_sequence +( + ZoO_index * sequence [const restrict static 1], + size_t sequence_size [const restrict static 1], + ZoO_index credits [const restrict], + const struct ZoO_knowledge k [const restrict static 1] +) +{ + ZoO_index sequence_length; + + sequence_length = (*sequence_size / sizeof(ZoO_index)); + + for (;;) + { + if ((credits == (ZoO_index *) NULL) || (*credits > 0)) + { + if (extend_right(sequence, *sequence_size, sequence_length, k) < 0) + { + /* Safe: (> sequence_length 1) */ + if (*sequence[(sequence_length - 1)] == ZoO_END_OF_SEQUENCE_ID) + { + /* + * We failed to add a word, but it was because none should have + * been added. + */ + return 0; + } + else + { + return -1; + } + } + } + else + { + /* No more credits available, we end the sequence. */ + *sequence[(sequence_length - 1)] = ZoO_END_OF_SEQUENCE_ID; + + return 0; + } + + /* + * Safe: if it was going to overflow, extend_left would have returned a + * negative value, making this statement unreachable. + */ + *sequence_size = (*sequence_size + sizeof(ZoO_index)); + sequence_length += 1; + + if (credits != (ZoO_index *) NULL) + { + *credits -= 1; + } + + /* Safe: (> sequence_length 1) */ + switch (*sequence[(sequence_length - 1)]) + { + case ZoO_START_OF_SEQUENCE_ID: + ZoO_S_WARNING + ( + "END OF LINE was added at the right part of an sequence." + ); + + *sequence[(sequence_length - 1)] = ZoO_END_OF_SEQUENCE_ID; + return 0; + + case ZoO_END_OF_SEQUENCE_ID: + return 0; + + default: + break; + } + } +} + +/******************************************************************************/ +/** INITIALIZING SEQUENCE *****************************************************/ +/******************************************************************************/ + +static int allocate_initial_sequence +( + ZoO_index * sequence [const restrict static 1], + size_t sequence_size [const restrict static 1], + const ZoO_index markov_order +) +{ + if ((SIZE_MAX / sizeof(ZoO_index)) > ((size_t) markov_order)) + { + ZoO_S_ERROR + ( + "Unable to store size of the initial sequence in a size_t variable." + "Either reduce the size of a ZoO_index or the markovian order." + ); + + *sequence = (ZoO_index *) NULL; + *sequence_size = 0; + + return -1; + } + + *sequence_size = ((size_t) markov_order) * sizeof(ZoO_index); + *sequence = (ZoO_index *) malloc(*sequence_size); + + if (*sequence == (void *) NULL) + { + *sequence_size = 0; + + ZoO_S_ERROR + ( + "Unable to allocate the memory required for an new sequence." + ); + + return -2; + } + + return 0; +} + +static int initialize_sequence +( + ZoO_index sequence [const restrict static 1], + const ZoO_index initial_word, + const ZoO_index markov_order, + const struct ZoO_knowledge k [const static 1] +) +{ + const ZoO_index * const restrict * restrict following_sequences; + const ZoO_index * restrict following_sequences_weights; + ZoO_index following_sequences_weights_sum; + ZoO_index chosen_sequence; + + sequence[0] = initial_word; + + if (markov_order == 1) + { + return 0; + } + + if + ( + ZoO_knowledge_get_following_sequences + ( + k, + initial_word, + &following_sequences, + &following_sequences_weights, + &following_sequences_weights_sum + ) < 0 + ) + { + ZoO_S_ERROR + ( + "Unable to find any sequence that would precede the initial word." + ); + + return -3; + } + + chosen_sequence = + weighted_random_pick + ( + following_sequences_weights, + following_sequences_weights_sum + ); + + /* Safe if 'allocate_initial_sequence' succeeded. */ + memcpy + ( + (void *) (sequence + 1), + (const void *) (following_sequences + chosen_sequence), + (((size_t) markov_order) - 1) * sizeof(ZoO_index) + ); + + return 0; +} + +/******************************************************************************/ +/** EXPORTED ******************************************************************/ +/******************************************************************************/ + +int ZoO_create_sequence_from +( + const ZoO_index initial_word, + ZoO_index credits [const restrict], + const struct ZoO_knowledge k [const restrict static 1], + const ZoO_index markov_order, + ZoO_index * sequence [const restrict static 1], + size_t sequence_size [const restrict static 1] +) +{ + if (allocate_initial_sequence(sequence, sequence_size, markov_order) < 0) + { + return -1; + } + + if (initialize_sequence(*sequence, initial_word, markov_order, k) < 0) + { + free((void *) *sequence); + *sequence_size = 0; + + return -2; + } + + if + ( + complete_right_part_of_sequence + ( + sequence, + sequence_size, + credits, + k + ) < 0 + ) + { + free((void *) *sequence); + *sequence_size = 0; + + return -3; + } + + if + ( + complete_left_part_of_sequence + ( + sequence, + sequence_size, + credits, + k + ) < 0 + ) + { + free((void *) *sequence); + *sequence_size = 0; + + return -4; + } + + if ((*sequence_size / sizeof(ZoO_index)) < 3) + { + /* 2 elements, for start and stop. */ + ZoO_S_ERROR("Created sequence was empty."); + + free((void *) *sequence); + *sequence_size = 0; + + return -5; + } + + return 0; +} diff --git a/src/core/index.h b/src/core/index.h new file mode 100644 index 0000000..76e3507 --- /dev/null +++ b/src/core/index.h @@ -0,0 +1,8 @@ +#ifndef _ZoO_CORE_INDEX_H_ +#define _ZoO_CORE_INDEX_H_ + +#include "index_types.h" + +ZoO_index ZoO_index_random_up_to (const ZoO_index limit); + +#endif diff --git a/src/core/index_types.h b/src/core/index_types.h new file mode 100644 index 0000000..2d769ca --- /dev/null +++ b/src/core/index_types.h @@ -0,0 +1,8 @@ +#ifndef _ZoO_CORE_INDEX_TYPES_H_ +#define _ZoO_CORE_INDEX_TYPES_H_ + +typedef unsigned int ZoO_index; + +#define ZoO_INDEX_MAX UINT_MAX + +#endif diff --git a/src/pervasive.h b/src/pervasive.h index f1dd5af..9e1faf7 100644 --- a/src/pervasive.h +++ b/src/pervasive.h @@ -43,8 +43,6 @@ #define ZoO_MARKOV_ORDER 3 #endif -typedef unsigned int ZoO_index; -#define ZoO_INDEX_MAX UINT_MAX /* ZoO_char = UTF-8 char */ typedef char ZoO_char; |