[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″]
This post is also available in: Greek
