C: Split a buffer to a list of segments of a specific size in bits
[download id=”2765″]
The following code will split a buffer in C
to a list of segments.
The size of the segments does not have to be a multiple of a byte.
User defines the size of the segments in bits
when calling node_t *segment(const unsigned char buffer[], const unsigned int buffer_bytes_size, const unsigned int segment_bit_size, const unsigned int first_segment_bit_size);
.
Each segment is an instance of element_t
structure as follows:
struct element_t { unsigned char *segment; unsigned int unused_bits; unsigned int size; };
Variable unused_bits
defines the bits in the last byte that should not be used in future operations.
[download id=”2765″]
Following is the code that performs the segmentation:
#include "segmentation.h" #include <math.h> #include <limits.h> #include <malloc.h> #include <string.h> //This method will create a string made of 0s and 1s representing the bits in an object. //It will skip printing the last n bits as per the input char *create_bit_representation_string(const void *object, const unsigned int size, const unsigned int skip_last_bits) { unsigned int i = 0; const unsigned char *byte; unsigned int temp_size = size; const double mask_filter = pow(2, skip_last_bits); const unsigned int skip_last_bytes = skip_last_bits / CHAR_BIT; char *result = malloc(sizeof(char) * size * CHAR_BIT - skip_last_bits + 1); for (byte = object; temp_size--; ++byte) { unsigned char mask; for (mask = 1 << (CHAR_BIT - 1); mask; mask >>= 1) { //We do not want to print the last n bits of the last byte as they should always be 0 if ((temp_size < skip_last_bytes) || (temp_size == 0 && mask < mask_filter)) { break; } result[i++] = (char) (mask & *byte ? '1' : '0'); } } result[i] = '\0'; return result; } //Creating a mask where the first n bits are 1s and the rest are 0s to zero the unused bits of the segment unsigned char create_left_mask(const unsigned int bits) { unsigned char left_mask = 0; unsigned int i; for (i = 0; i < bits; i++) { left_mask |= (1 << (CHAR_BIT - 1 - i)); } return left_mask; } //This function will shift to the left a char array for up to 7 bits. //It will update the object and return the number of bits shifted unsigned int shift_left_char_array_n_bits(void *object, const unsigned int size, const unsigned int bits) { if (bits == 0) { return 0; } if (bits < 1 || bits > CHAR_BIT - 1) { fprintf(stderr, "%s: Bad value %u for 'bits', it should be [1,7]" "\n\tIgnoring operation\n", __FUNCTION__, bits); return 0; } //Creating a mask where the first n bits are 1s and the rest are 0s. const unsigned char left_mask = create_left_mask(bits); unsigned char *byte; unsigned int temp_size = size; //We use temp_size as a counter (until it reaches 0) and we move the byte pointer at each loop for (byte = object; temp_size--; ++byte) { unsigned char carry = 0; if (temp_size) { //We get the bits we want to carry using the mask carry = byte[1] & left_mask; //Then shift them to the right, as this is where they will be in the new byte. carry >>= (CHAR_BIT - bits); } //Shifting the new byte to make space for the carry *byte <<= bits; //Applying carry *byte |= carry; } return bits; } const unsigned int calculate_unused_bits(const unsigned int segment_bit_size) { return (CHAR_BIT - (segment_bit_size % CHAR_BIT)) % CHAR_BIT; } element_t *create_element(const unsigned char buffer[], const unsigned int byte_size, const unsigned int unused_bits, const unsigned int bytes_skipped, const unsigned char left_mask) { element_t *element = (element_t *) malloc(sizeof(element_t)); element->segment = malloc(byte_size); element->size = byte_size; element->unused_bits = unused_bits; memcpy(element->segment, &(buffer[bytes_skipped]), byte_size); //Zeroing the unused bits at the end of the segment element->segment[byte_size - 1] &= left_mask; return element; } //This method will split a buffer to segments of specific size in bits and it will return them as a list //(each element contains the segment data, its size in bytes and the number of bits that are not used from the last byte) //If the input buffer is less than the segment size, it will return one segment with all the data. //The user can set the bit size of the first segment to be different than the rest using first_segment_bit_size > 0 node_t *segment(const unsigned char buffer[], const unsigned int buffer_bytes_size, const unsigned int segment_bit_size, const unsigned int first_segment_bit_size) { if (buffer_bytes_size == 0) { fprintf(stderr, "%s: Bad value %u for 'buffer_bytes_size', it should be greater than 0" "\n\tIgnoring operation\n", __FUNCTION__, buffer_bytes_size); return NULL; } if (segment_bit_size == 0) { fprintf(stderr, "%s: Bad value %u for 'segment_bit_size', it should be greater than 0" "\n\tIgnoring operation\n", __FUNCTION__, segment_bit_size); return NULL; } node_t *head = NULL; const double char_bit = CHAR_BIT; const unsigned int first_segment_byte_size = (unsigned int) ceil( first_segment_bit_size / char_bit); if (first_segment_byte_size > buffer_bytes_size) { append(&head, create_element(buffer, buffer_bytes_size, 0, 0, UCHAR_MAX)); return head; } unsigned char *temp_buffer = malloc(buffer_bytes_size); memcpy(temp_buffer, buffer, buffer_bytes_size); unsigned int bits_shifted = 0; unsigned int bytes_skipped = 0; if (first_segment_bit_size > 0) { const unsigned int first_segment_unused_bits = calculate_unused_bits( first_segment_bit_size); const unsigned int first_segment_byte_size_without_incomplete_byte = first_segment_bit_size / CHAR_BIT; const unsigned int first_segment_bits = CHAR_BIT - first_segment_unused_bits; const unsigned char left_mask = create_left_mask(first_segment_bits); append(&head, create_element(temp_buffer, first_segment_byte_size, first_segment_unused_bits, bytes_skipped, left_mask)); bytes_skipped += first_segment_byte_size_without_incomplete_byte; if (bytes_skipped == buffer_bytes_size) { free(temp_buffer); return head; } if (first_segment_bits > 0 && first_segment_bits < CHAR_BIT) { bits_shifted += shift_left_char_array_n_bits(&(temp_buffer[bytes_skipped]), buffer_bytes_size - bytes_skipped - (bits_shifted / CHAR_BIT), first_segment_bits); } } const unsigned int segment_byte_size = (unsigned int) ceil(segment_bit_size / char_bit); const unsigned int buffer_bits_size = (buffer_bytes_size - bytes_skipped) * CHAR_BIT - bits_shifted; const unsigned int segments_count = buffer_bits_size / segment_bit_size; if (segments_count == 0) { append(&head, create_element(temp_buffer, buffer_bytes_size - bytes_skipped, bits_shifted, bytes_skipped, UCHAR_MAX)); free(temp_buffer); return head; } //Creating a mask where first n bits are 1s and the rest are 0s to zero the unused bits of the segment const unsigned int segment_unused_bits = calculate_unused_bits(segment_bit_size); const unsigned int last_segment_bits = CHAR_BIT - segment_unused_bits; const unsigned char left_mask = create_left_mask(last_segment_bits); const unsigned int segment_byte_size_without_incomplete_byte = segment_bit_size / CHAR_BIT; const unsigned int extra_bits = buffer_bits_size % segment_bit_size; unsigned int i; for (i = 0; i < segments_count; i++) { append(&head, create_element(temp_buffer, segment_byte_size, segment_unused_bits, bytes_skipped, left_mask)); bytes_skipped += segment_byte_size_without_incomplete_byte; if ((segments_count > 1 || extra_bits > 0) && (last_segment_bits > 0 && last_segment_bits < CHAR_BIT)) { bits_shifted += shift_left_char_array_n_bits(&(temp_buffer[bytes_skipped]), buffer_bytes_size - bytes_skipped - (bits_shifted / CHAR_BIT), last_segment_bits); } } if (extra_bits) { const unsigned int last_segment_bytes_size = buffer_bytes_size - bytes_skipped - (bits_shifted / CHAR_BIT); const unsigned int unused_bytes_for_last_segment = segment_byte_size - last_segment_bytes_size; const unsigned int last_segment_unused_bits = segment_bit_size - (buffer_bits_size % segment_bit_size) + segment_unused_bits - (unused_bytes_for_last_segment * CHAR_BIT); append(&head, create_element(temp_buffer, last_segment_bytes_size, last_segment_unused_bits, bytes_skipped, UCHAR_MAX)); } free(temp_buffer); return head; }
Sample code that uses the function:
#include <stdio.h> #include <malloc.h> #include <string.h> #include <limits.h> #include <stdlib.h> #include <time.h> #include "libs/segmentation/segmentation.h" // This application will create a char array of size BUFFER_BYTE_SIZE that contains random values // and later it will split it in segments of size SEGMENT_BIT_SIZE. // The first segment will be of size FIRST_SEGMENT_BIT_SIZE. #define BUFFER_BYTE_SIZE 420 #define SEGMENT_BIT_SIZE 222 #define FIRST_SEGMENT_BIT_SIZE 11 #define POSSIBLE_VALUES 256 int main() { srand(time(NULL)); const unsigned int buffer_byte_size = BUFFER_BYTE_SIZE; fprintf(stdout, "Buffer Size: %uB\n", buffer_byte_size); const unsigned int segment_bit_size = SEGMENT_BIT_SIZE; fprintf(stdout, "Segment Size: %ub\n", segment_bit_size); const unsigned int first_segment_bit_size = FIRST_SEGMENT_BIT_SIZE; fprintf(stdout, "First Segment Size: %ub\n", first_segment_bit_size); unsigned char buffer[buffer_byte_size]; unsigned int i; for (i = 0; i < buffer_byte_size; i++) { buffer[i] = (unsigned char) (rand() % POSSIBLE_VALUES); } char *buffer_bits = create_bit_representation_string(buffer, buffer_byte_size, 0); const size_t buffer_length = strlen(buffer_bits); fprintf(stdout, "\tBuffer: '%s'\n", buffer_bits); node_t *head = segment(buffer, buffer_byte_size, segment_bit_size, first_segment_bit_size); element_t *element = pop(&head); unsigned int bytes_skipped = 0; unsigned int segment_count = 0; unsigned int total_segment_bit_size = 0; while (element != NULL) { char *segment_bits = create_bit_representation_string(element->segment, element->size, element->unused_bits); const size_t segment_length = strlen(segment_bits); fprintf(stdout, "\t\tSegment %04u: Size in bytes %02u - Unused bits %04u - '%.*s'\n", ++segment_count, element->size, element->unused_bits, element->size * CHAR_BIT - element->unused_bits, segment_bits); if (segment_length == 0) { fprintf(stderr, "Data validation failed." "\n\tBuffer size in bytes %d" "\n\tSegment size in bits %d" "\n\tFirst Segment size in bits %d" "\n\tFound empty segment\n", buffer_byte_size, segment_bit_size, first_segment_bit_size); clear(&head); free(segment_bits); free(element->segment); free(element); free(buffer_bits); return EXIT_FAILURE; } for (i = 0; i < segment_length && bytes_skipped + i < buffer_length; i++) { if (segment_bits[i] != buffer_bits[bytes_skipped + i]) { fprintf(stderr, "Data validation failed." "\n\tBuffer size in bytes %d" "\n\tSegment size in bits %d" "\n\tFirst Segment size in bits %d" "\n\tPosition %u of the buffer" "\n\tPosition %u of the segment\n", buffer_byte_size, segment_bit_size, first_segment_bit_size, bytes_skipped + i, i); clear(&head); free(segment_bits); free(element->segment); free(element); free(buffer_bits); return EXIT_FAILURE; } } free(segment_bits); bytes_skipped += segment_length; const unsigned int current_segment_bit_size = ((element->size - 1) * CHAR_BIT) + CHAR_BIT - element->unused_bits; if (segment_length != current_segment_bit_size) { fprintf(stderr, "Data validation failed." "\n\tBuffer size in bytes %d" "\n\tSegment size in bits %d" "\n\tFirst Segment size in bits %d" "\n\tCurrent Segment bit size (%u) not equal to its string representation (%lu)\n", buffer_byte_size, segment_bit_size, first_segment_bit_size, current_segment_bit_size, segment_length); clear(&head); free(segment_bits); free(element->segment); free(element); free(buffer_bits); return EXIT_FAILURE; } total_segment_bit_size += current_segment_bit_size; free(element->segment); free(element); element = pop(&head); } free(buffer_bits); if (buffer_length != total_segment_bit_size) { fprintf(stderr, "Data validation failed." "\n\tBuffer size in bytes %d" "\n\tSegment size in bits %d" "\n\tFirst Segment size in bits %d" "\n\tTotal Segment bit size (%u) not equal to full string representation (%lu)\n", buffer_byte_size, segment_bit_size, first_segment_bit_size, total_segment_bit_size, buffer_length); return EXIT_FAILURE; } return EXIT_SUCCESS; }
[download id=”2765″]