C Program need explanation

Discussion in 'Programming & Hardware' started by creativeself, Nov 21, 2015.

  1. This is a program which combines all possible letter+number combinations to a set length of characters. I sort of understand what is going on but the 'bruteSequential' function confuses me...don't quite understand that. Was wondering if someone could explain

    Code (Text):
    1. #include <stdio.h>
    2. #include <string.h>
    3. #include <stdlib.h>
    4.  
    5.  
    6. static const char alphabet[] =
    7. "abcdefghijklmnopqrstuvwxyz"
    8. "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    9. "0123456789";
    10.  
    11. static const int alphabetSize = sizeof(alphabet) - 1;
    12.  
    13. void bruteImpl(char* str, int index, int maxDepth)
    14. {
    15.     for (int i = 0; i < alphabetSize; ++i){
    16.         str[index] = alphabet[i];
    17.  
    18.         if (index == maxDepth - 1) printf("%s\n", str);
    19.         else bruteImpl(str, index + 1, maxDepth);
    20.     }
    21. }
    22.  
    23. void bruteSequential(int maxLen)
    24. {
    25.     char* buf = malloc(maxLen + 1);
    26.  
    27.     for (int i = 1; i <= maxLen; ++i){
    28.         memset(buf, 0, maxLen + 1);
    29.         bruteImpl(buf, 0, i);
    30.     }
    31.  
    32.     free(buf);
    33. }
    34.  
    35. int main(void)
    36. {
    37.     int x;
    38.     printf("Length: \n");
    39.     scanf("%x",&x);
    40.     bruteSequential(x);
    41.  
    42.     return 0;
    43. }
    44.  
    45.  
     
  2. malloc() is a memory allocation function that accepts the number of bytes to allocate as the parameter.
    memset() is a function to store data at a specific address; 'buf' being the destination, '0' being the data to store, and maxLen+1 being the size of the data to store. The purpose of this is to prevent dirty memory, which is when you have previously stored data in a pointer.
    Then it stores the possible combinations of characters at this location.
     
  3. To add onto what @Coma said, there are a few things here that should have been clarified by the original writer.

    The reason the memory allocation is maxLen + 1 is because strings in C need to be null-terminated. This refers to ending the string with the \0 character. More specifically, this is needed because printf will print up to (but not including) the null-terminator. So if it isn't there, you get undefined behavior.

    Consider the following:

    Code (Text):
    1. #include <stdio.h>
    2. #include <stdlib.h>
    3.  
    4. int main()
    5. {
    6.     size_t bufferSize;
    7.     char * buffer;
    8.    
    9.     bufferSize = 5;
    10.     buffer = (char *) malloc(bufferSize);
    11.    
    12.     buffer[0] = 'a';
    13.     buffer[1] = 'b';
    14.     buffer[2] = 'c';
    15.     buffer[3] = 'd';
    16.     buffer[4] = 'e';
    17.    
    18.     printf("%s", buffer);
    19.    
    20.     free(buffer);
    21.  
    22.     return 0;
    23. }
    This is prone to undefined behavior as a null-terminator is never included. The full buffer is allocated with non-zero characters. Now, seeing as this program is so simple it is unlikely to run into issues as most of the memory will be empty. However, proper precautions should always be taken.

    ---

    After that, the loop runs through and clears the buffer. This is where the null-terminator is added, as the entire buffer is initialized to 0, so there will always be at least one \0 present in the buffer (assuming the maximum length is respected).

    The actual implementation is then called. Blah blah blah, prints out some permutations.

    The buffer is then freed so the allocater can now reuse that memory.

    ---

    By reusing the buffer we can force undefined behavior. You'll notice that some extra character(s) get printed out at the end that shouldn't be printed. This is because I purposefully forgot the null-terminator.

    Code (Text):
    1. #include <stdio.h>
    2. #include <stdlib.h>
    3.  
    4. int main()
    5. {
    6.     size_t bufferSize;
    7.     char * buffer;
    8.    
    9.     bufferSize = 5;
    10.     buffer = (char *) malloc(bufferSize);
    11.    
    12.     buffer[0] = 'a';
    13.     buffer[1] = 'b';
    14.     buffer[2] = 'c';
    15.     buffer[3] = 'd';
    16.     buffer[4] = 'e';
    17.    
    18.     printf("%s\n", buffer);
    19.    
    20.     bufferSize = 3;
    21.     buffer = (char *) malloc(bufferSize);
    22.  
    23.     buffer[0] = 'z';
    24.     buffer[1] = 'y';
    25.  
    26.     printf("%s", buffer);
    27.  
    28.     free(buffer);
    29.  
    30.     return 0;
    31. }
    It gave results such as:

    Code (Text):
    1. abcde
    2. zy~
    Code (Text):
    1. abcde
    2. zy>
    And a few others.
     
  4. hey coma!!! im your biggest fan!!!
     

Share This Page

Loading...