ex1a2.c File Reference

Appfs Exercise 1: direct read input, big endian is handled, use of int32_t and uint32_t. More...

#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <limits.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>
#include <assert.h>

Go to the source code of this file.

Macros
#define	MAX_NUMS   ((INT32_MAX >> 5) + 1)
	Maximum number of 32 bit ints we need to store bits. More...
#define	BUF_NUMS   4096
	read buffer size More...

Functions
static bool	is_little_endian (void)
	Check if the architecture is little endian. More...
static int32_t	reverse_int32 (int32_t val)
	Reverse the 4 bytes of an int between little and big endian. More...
int	main (int argc, char **argv)
	Program to read a file with binary positive 32 bit integers, sort the numbers and print them sorted. More...

Detailed Description

Author

Thorsten Koch

Date

24Oct2014

gcc -O3 -Wall -std=c99 -o ex1a2 ex1a2.c

Using direct read() for input Improvements to ex1a: big endian is handled, use of int32_t and uint32_t. Adding of static inline.

Definition in file ex1a2.c.

Macro Definition Documentation

#define BUF_NUMS   4096

Definition at line 24 of file ex1a2.c.

#define MAX_NUMS   ((INT32_MAX >> 5) + 1)

Definition at line 23 of file ex1a2.c.

Function Documentation

static bool is_little_endian ( void  )

inlinestatic

This check is constant and can be optimized away by the compiler during compile time. All conditionals depending on it are then decided at compile time

Returns

true if the machine uses little endian, false otherwise.

Definition at line 31 of file ex1a2.c.

{
   union { uint32_t u; char c[sizeof(uint32_t)]; } bint = { 0x01020304 };

   return bint.c[0] == 4; 
}

int main	(	int	argc,
		char **	argv
	)

Actually, the numbers are not sorted. There is an array with one bit for each possible number. Upon reading the respective bit is set for the number recognized. At the end the array is scanned in order and the numbers present are printed.

Parameters

argv	[1] name of file to read

Definition at line 58 of file ex1a2.c.

{
   const char* usage = "usage: %s filename\n";

   /* made static, because otherwise, the stack size might be too small.
    */
   static uint32_t have_num[MAX_NUMS];
   
   int32_t buf[BUF_NUMS];
   int     fd;
   int     n;
   int     total_nums = 0;

   /* we assume 32 bit integers, otherwise it will not work
    */
   assert(sizeof(int) >= 4);
   
   /* Check arguments, we need a filename.
    */
   if (argc < 2)
   {
      fprintf(stderr, usage, argv[0]);
      exit(EXIT_FAILURE);
   }
   memset(have_num, 0, sizeof(have_num)); // Proably uneccessary

   /* Open file
    */
   if (0 > (fd = open(argv[1], O_RDONLY)))
   {
      perror(argv[1]);
      exit(EXIT_FAILURE);
   }

   /* Read from file until data exhausted
    */
   while(0 < (n = read(fd, buf, sizeof(buf))))
   {
      int nums_read = n / sizeof(buf[0]); 

      assert(nums_read <= BUF_NUMS);
      
      total_nums += nums_read;

      /* Run through buffer of read numbers and set mark bits
       */
      for(int i = 0; i < nums_read; i++)
      {
         int32_t num = buf[i];

         if (!is_little_endian())
            num = reverse_int32(num);
         
         // fprintf(stderr, "%d\n", num);

         /* Check input: really >= 0 ? Otherwise ignore
          */
         if (num >= 0)
         {
            int      idx = num >> 5;         // n / 32
            uint32_t msk = 1 << (num & 31);  // bit number n mod 32 

            assert(idx >= 0 && idx < MAX_NUMS);
            
            have_num[idx] |= msk;
         }
      }
   }
   if (close(fd))
   {
      perror("close: ");
      exit(EXIT_FAILURE);
   }
   fprintf(stderr, "Total numbers read = %d\n", total_nums);
   
   for(int i = 0; i < MAX_NUMS; i++)
      if (have_num[i])  // just for speed up
         for(int k = 0; k < 31; k++)
            if (have_num[i] & (1 << k))
               printf("%d\n", (i << 5) + k);

   return EXIT_SUCCESS;
}

static int32_t reverse_int32 ( int32_t  val )

inlinestatic

Byte order 1 2 3 4 ist reversed to 4 3 2 1

Parameters

val	value to be reversed

Returns

reversed value

Definition at line 43 of file ex1a2.c.

{
    val = ((val << 8) & 0xFF00FF00) | ((val >> 8) & 0xFF00FF);
    
    return (val << 16) | ((val >> 16) & 0xFFFF);
}