#StackBounty: #c #strings #file #steganography Simple program to hide messages in files (steganography)

Bounty: 50

That is a simple program to hide text messages in text files. I’d like to hear any advices to improve my code and style.

Some notes:

  1. There is no error handling to simplify the program. It is not a «real» program anyway. There is many assertions instead error handling.
  2. I wrote my own implementations to strdup and strrev because these functions are not a part of ISO C. I called they as reverseString and duplicateString corresponding since names like str* is reserved by ISO C.
  3. I check the validity of input arguments in functions to prevent mistakes of using internal API.
  4. All the functions marked as static because all they in a single translation unit.

And one another question: the input file should be opened in text mode while temporary file is always opens in binary mode (w+b). Could it lead to some problems?

Compiler

I’m using Clang to compile the program with such flags:

-std=c11
-Weverything
-Wpedantic
-fsanitize=address
-D_CRT_SECURE_NO_WARNINGS

It gives only one warning:

warning: implicit conversion turns floating-point number into integer: 'double' to 'size_t' (aka 'unsigned int') [-Wfloat-conversion]
        const size_t newCapacity = ceil(s->capacity * DYNAMIC_STRING_GROW_FACTOR);

Static code analyzer

Also I have checked the code by CppCheck and it gives only one error: «Memory leak: ret in function stringToBinary»:

char *stringToBinary(const char *s)
{
    assert(s);
    assert(strlen(s) > 0);

    char *ret = calloc((strlen(s) + 1) * CHAR_BIT + 1, 1);
    assert(ret);

    for (size_t i = 0; s[i] != ''; i++)
        strcat(ret, charToBinary(s[i]));

    return strcat(ret, charToBinary(''));
}

But I think it is a false positive because ret is freed in the hideMessage function:

char *msgBinary = stringToBinary(msg);
...
free(msgBinary);

I’ll be glad if you give me any tips to improve my code or correct my mistakes. Thanks you in advance! Best regards 🙂

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <assert.h>

#define DYNAMIC_STRING_GROW_FACTOR 1.5

typedef struct DynamicString {
    char *s;
    size_t capacity;
    size_t length;
} DynamicString;

static void  createDynamicString(DynamicString *, size_t);
static void  destroyDynamicString(DynamicString *);
static void  increaseDynamicStringCapacity(DynamicString *);
static void  appendCharToDynamicString(DynamicString *, char);
static void  hideMessage(FILE *, const char *);
static char *extractMessage(FILE *);
static void  copyFile(FILE *, FILE *);
static char *stringToBinary(const char *);
static char *charToBinary(char);
static char  charFromBinary(const char *);
static char *reverseString(char *);
static char *duplicateString(const char *s);

int main(void)
{
    FILE *file = fopen("file.txt", "r+");
    assert(file);

    hideMessage(file, "hello, world");

    char *msg = extractMessage(file);
    assert(msg);
    puts(msg);

    free(msg);
    fclose(file);
}

/* The HIDEMESSAGE function
 *
 * The function hides text message into the file by that way: 1) the message
 * converts to binary; 2) each bit of the converted message writes at the end
 * of each file's line (right before the new-line character): if the bit
 * is 1 then a space (' ') appends to the line otherwise it's nothing appends
 * to the line.
 *
 * Assumes the the file does not contain any spaces right before new-line
 * characters. Also assumes that the file has enough lines for storing
 * the message.
 */
void hideMessage(FILE *f, const char *msg)
{
    assert(f);
    assert(msg);
    assert(strlen(msg) > 0);

    char *msgBinary = stringToBinary(msg);
    assert(msgBinary);

    FILE *tempFile = tmpfile();
    assert(tempFile);

    for (int ch, i = 0; (ch = fgetc(f)) != EOF;) {
        if (msgBinary[i] && (ch == 'n'))
            if (msgBinary[i++] == '1')
                fputc(' ', tempFile);

        fputc(ch, tempFile);
    }

    copyFile(f, tempFile);

    free(msgBinary);
    fclose(tempFile);
}

/* The EXTRACTMESSAGE function
 *
 * The function extracts message hidden by the HIDEMESSAGE function from
 * the input file and returns a pointer to heap-allocated string which
 * contains the message.
 */
char *extractMessage(FILE *f)
{
    assert(f);

    DynamicString msgBuffer;
    createDynamicString(&msgBuffer, 128);

    char charInBinary[CHAR_BIT + 1] = {0};

    for (int prevCh = 0, ch, i = 0; (ch = fgetc(f)) != EOF; prevCh = ch) {
        if (ch == 'n')
            charInBinary[i++] = (prevCh == ' ') ? '1' : '0';

        if (i % CHAR_BIT == 0 && i != 0) {
            if (!strcmp(charInBinary, charToBinary('')))
                break;

            i = 0;
            appendCharToDynamicString(&msgBuffer, charFromBinary(charInBinary));
        }
    }

    char *ret = duplicateString(msgBuffer.s);
    assert(ret);

    destroyDynamicString(&msgBuffer);
    return ret;
}

/* The CREATEDYNAMICSTRING function
 *
 * The function initializes a DynamicString passing by the first argument.
 * The initial capacity of the string is passing by the second argument.
 * Capacity is the max length of the string. At the same time length is
 * current length of the string. Thus the function allocates capacity + 1
 * bytes for the string (considering the null-character).
 *
 * The input pointer to DynamicString struture should be a valid pointer and
 * capacity should be greater than 0.
 */
void createDynamicString(DynamicString *ret, size_t capacity)
{
    assert(ret);
    assert(capacity > 0);

    ret->s = malloc(capacity + 1);
    assert(ret->s);

    ret->length = 0;
    ret->capacity = capacity;
}

/* The APPENDCHARTODYNAMICSTRING function
 *
 * The function appends a character to the input DynamicString. If capacity of
 * the string is not enough the function increases it.
 *
 * The input pointer to a DynamicString should be a valid pointer as well as
 * its string buffer.
 */
void appendCharToDynamicString(DynamicString *s, char c)
{
    assert(s);
    assert(s->s);

    if (s->length == s->capacity)
        increaseDynamicStringCapacity(s);

    s->s[s->length++] = c;
    s->s[s->length] = '';
}

/* The INCREASEDYNAMICSTRINGCAPACITY function
 *
 * The function increases capacity of the input DynamicString. Grow factor
 * is sets by a macro constant DYNAMIC_STRING_GROW_FACTOR.
 *
 * The input pointer to a DynamicString struture should be a valid pointer
 * as well as its string buffer.
 */
void increaseDynamicStringCapacity(DynamicString *s)
{
    assert(s);
    assert(s->s);

    const size_t newCapacity =  ceil(s->capacity * DYNAMIC_STRING_GROW_FACTOR);

    s->s = realloc(s->s, newCapacity + 1);
    assert(s->s);

    s->capacity = newCapacity;
}

/* The DESTROYDYNAMICSTRING function
 *
 * The function destroys the input DynamicString. It frees the string buffer
 * of the input DynamicString.
 *
 * The input pointer to a DynamicString should be a valid pointer as well as
 * its string buffer.
 */
void destroyDynamicString(DynamicString *s)
{
    assert(s);
    assert(s->s);

    free(s->s);
}

/* The COPYFILE function
 *
 * The function copies all the contents of src to dest. Both arguments should
 * be valid pointers. dest should be open for writing, src should be open
 * for reading. The function does not close the files. The both file cursor
 * position sets to the beginning.
 */
void copyFile(FILE *dest, FILE *src)
{
    assert(dest);
    assert(src);

    rewind(dest);
    rewind(src);

    for (int ch; (ch = fgetc(src)) != EOF;)
        fputc(ch, dest);

    rewind(dest);
    rewind(src);
}

/* The CHARFROMBINARY function
 *
 * The function converts the input string returned by the CHARTOBINARY function
 * to a character.
 *
 * The input string should be a valid null-terminated string and its length
 * should be greater 0.
 *
 * charFromBinary(charToBinary(c)) == c
 */
char charFromBinary(const char *s)
{
    assert(s);
    assert(strlen(s) > 0);

    char ret = 0;
    unsigned int p = 1;

    for (size_t i = strlen(s); i-- > 0; p *= 2)
        if (s[i] == '1')
            ret += p;

    return ret;
}

/* The STRINGTOBINARY function
 *
 * The function converts the input string to binary form and returns a pointer
 * to heap-allocated null-terminated string. Null-terminator of the input
 * string also converts to binary form and appends to the result. The caller
 * should free memory allocated for the output string.
 *
 * The input string should be a valid null-terminated string and its length
 * should be greater 0.
 *
 * stringToBinary("cat") => "01100011011000010111010000000000"
 * stringToBinary("dog") => "01100100011011110110011100000000"
 * stringToBinary("R") => "0101001000000000"
 */
char *stringToBinary(const char *s)
{
    assert(s);
    assert(strlen(s) > 0);

    char *ret = calloc((strlen(s) + 1) * CHAR_BIT + 1, 1);
    assert(ret);

    for (size_t i = 0; s[i] != ''; i++)
        strcat(ret, charToBinary(s[i]));

    return strcat(ret, charToBinary(''));
}

/* The CHARTOBINARY function
 *
 * The function converts value of the input character to binary form and
 * returns a pointer to the static null-terminated string which contains
 * the result. The result contains leading zeroes.
 *
 * charToBinary(100) => "01100100"
 * charToBinary('A') => "01000001"
 * charToBinary('') => "00000000"
 */
char *charToBinary(char c)
{
    static char ret[CHAR_BIT + 1];

    memset(ret, '0', sizeof ret);
    ret[sizeof ret - 1] = '';

    for (size_t i = 0; c; i++) {
        ret[i] = (c % 2) ? '1' : '0';
        c /= 2;
    }

    return reverseString(ret);
}

/* The REVERSESTRING function
 *
 * The input string should be a valid pointer to a null-terminated string.
 * If the input string is empty the function does noting.
 *
 * reverseString("hello") => "olleh"
 * reverseString("a") => "a"
 * reverseString("") => "a"
 */
char *reverseString(char *s)
{
    assert(s);

    char *begin = s;
    char *end = s + strlen(s) - 1;

    for (; begin < end; begin++, end--) {
        const char t = *begin;
        *begin = *end;
        *end = t;
    }

    return s;
}

/* The DUPLICATESTRING function
 *
 * The function returns a pointer to a heap-allocated string, which is a
 * duplicate of the input string. The returned pointer can be passed to the
 * free function.
 */
char *duplicateString(const char *s)
{
    assert(s);
    assert(strlen(s) > 0);

    char *copy = malloc(strlen(s) + 1);
    assert(copy);

    return strcpy(copy, s);
}

P.S. I’m not a native English speaker so… sorry for the inconvenience.


Get this bounty!!!

Convert Comma separated String to Rows in Oracle SQL

Many times we need to convert a comma separated list of terms in a single string and convert it rows in SQL query.

for example

 India, USA, Russia, Malaysia, Mexico

Needs to be converted to:

 Country
 India
 USA
 Russia
 Malaysia
 Mexico

The following SQL script can help in this:

just replace the required values with your string and your delimiter.

HackerRank: Repeated String

Problem

Lilah has a string, s, of lowercase English letters that she repeated infinitely many times.

Given an integer, n, find and print the number of letter a‘s in the first letters of Lilah’s infinite string.

Input Format

The first line contains a single string, s.
The second line contains an integer, n.

Constraints

  • 1<=|s|<=100
  • 1<=|n|<=10^12
  • For 25% of the test cases, n <= 10^6

Output Format

Print a single integer denoting the number of letter a’s in the first letters of the infinite string created by repeating infinitely many times.

Sample Input 0

aba
10

Sample Output 0

7

Explanation 0

The first n = 10 letters of the infinite string are abaabaabaa. Because there are 7 a‘s, we print on a new line.

Sample Input 1

a
1000000000000

Sample Output 1

1000000000000

Explanation 1

Because all of the first n=1000000000000 letters of the infinite string are a, we print 1000000000000 on a new line.

Solution

CodeEval: Penultimate Word

Challenge Description:

Write a program which finds the next-to-last word in a string.

Input Sample:

Your program should accept as its first argument a path to a filename. Input example is the following

some line with text
another line

Each line has more than one word.

Output Sample:

Print the next-to-last word in the following way.

with
another

Solution:

 

CodeEval: Shortest Repetition

Challenge Description:

Write a program to determine the shortest repetition in a string.
A string is said to have period p if it can be formed by concatenating one or more repetitions of another string of length p. For example, the string “xyzxyzxyzxyz” has period 3, since it is formed by 4 repetitions of the string “xyz”. It also has periods 6 (two repetitions of “xyzxyz”) and 12 (one repetition of “xyzxyzxyzxyz”).

Input Sample:

Your program should accept as its first argument a path to a filename. Each line will contain a string of up to 80 non-blank characters. E.g.

abcabcabcabc
bcbcbcbcbcbcbcbcbcbcbcbcbcbc
dddddddddddddddddddd
adcdefg

Output Sample:

Print out the smallest period of the input string. E.g.

3
2
1
7

Solution:

 

HackerRank: Alternating Characters

Problem

Shashank likes strings in which consecutive characters are different. For example, he likes ABABA, while he doesn’t like ABAA. Given a string containing characters A and B only, he wants to change it into a string he likes. To do this, he is allowed to delete the characters in the string.

Your task is to find the minimum number of required deletions.

Input Format

The first line contains an integer T, i.e. the number of test cases.
The next T lines contain a string each.

Output Format

For each test case, print the minimum number of deletions required.

Constraints

1T10
1≤ length of string 10^5

Sample Input

5
AAAA
BBBBB
ABABABAB
BABABA
AAABBB

Sample Output

3
4
0
0
4

Explanation

AAAA A, 3 deletions
BBBBB B, 4 deletions
ABABABAB ABABABAB, 0 deletions
BABABA BABABA, 0 deletions
AAABBB AB, 4 deletions because to convert it to AB we need to delete 2 A’s and 2 B’s

Solution

Combinations of a String

Problem:
Write an algorithm to print all possible combinations of characters in a string.

Solution:
Since we need to generate combinations, we can start with a single character and then continue to add a character to combinations we have seen so far.

Let’s use “XYZ” as an example.

public void buildTree(String input, StringBuffer output, int k)
{
    for (int i = k; i < input.length(); i++)
    {
        output.append(input.charAt(i));
        buildTree(input, output, i + 1);
        output.deleteCharAt(output.length() - 1);
    }
} 

public static void main(String[] args){
     buildTree("XYZ", new StringBuffer(), 0);
}

Dry Run just to give an idea:

X–>Y–>Z
–>Z–>Y

Y–>X–>Z
–>Z–>X

Z–>Y–>X
–>X–>Y

How to replace in Javascript, when replacement string is a variable

How to replace in Javascript, when replacement string is a variable

Very often we use replace method in javascript while replacing a string literal by another string literal.
But what if we need to replace a string whose value is held in a variable.

Here is the solution…

You can use a regular expression (often referred to as a RegEx or a RegExp). Regular expressions are much more powerful than standard string matching as they can use very complicated logic

// Let's take a look at the above example using regular expressions.
strReplaceSimple = strText.replace( new RegExp( "th", "" ), "[X]" );

alert( strReplaceSimple );

As you can see, we have the same replace happening. So let’s take a look at what’s going on. Instead of passing simple target string to the replace() method, we are passing in a regular expression (new RegExp()) object instance. The RegExp() takes two arguments, the expression and the search flags (left blank in our example). There are two universally valid flags: [g] which means globally replace and [i] which
means case INsensitive. By default, the regular expression is NOT global and case sensitive.

// So let's try to do a global replace using regular expressions.
strReplaceAll = strText.replace( new RegExp( "th", "g" ), "[X]" );

alert( strReplaceAll );

We just did a global replace in ONE line of code.

strReplaceAll = strText.replace( new RegExp( "th", "gi" ), "[X]" );

alert( strReplaceAll );

We just replaced out that additional “Th” simply by adding the flag [i] into the regular expression. That’s how powerful regular expressions are. But there’s more. Regular expressions are more than just flags. Much more!

Image that for some reason, you knew about regular expressions, but you didn’t know about the case insensitive flag [i]. You could have performed the same replace using this:

strReplaceAll = strText.replace( new RegExp( "(T|t)(H|h)", "g" ), "[X]" );

alert( strReplaceAll );

This groups the two letters together, and for each letter it tells the replacing algorithm to match t OR T followed by h OR H. There is sooo much more that regular expressions can do. Unfortunately, that is outside the scope of this entry. You should really look into regular expression both in Javascript and in ColdFusion / Java. They are amazing.

But what happens if you don’t want to do a simple replace? The replace method allows some very interesting flexibility. Up until now, we have been passing a simple string in a the “replace-in” argument ([X]). But, you don’t have to. You can pass in a function pointer instead.

For this example, let’s replace out the target string with a random letter in the brackets, not necessarily the X. First we have to create a function that will return the resultant random string

function RandomString(){
// Create an array of letters.
var arrLetters = ["A","B","C","D","E","V","W","X","Y","Z"];

// Use the random() method and the modulus (%) operator to
// pick a random letter from the above array.
var intLetter = (Math.floor( Math.random() * 10 ) % 9);

// Return the random letter string we get from the
// array of letters above.
return( "[" + arrLetters[ intLetter ] + "]" );
}

Try calling the function on its own a few times, just to see how it behaves.

alert(
RandomString() + "n" + RandomString() + "n" +
RandomString() + "n" + RandomString() + "n" +
RandomString() + "n" + RandomString() + "n" +
RandomString() + "n" + RandomString() + "n"
);

As you can see, it randomly (as random as possible) picks a letter to return. Now, let’s call the replace with the RandomString() method sent as the second argument. We will do this a few times so you can see the randomness in effect.

alert( strText.replace( "th", RandomString ) );
alert( strText.replace( "th", RandomString ) );
alert( strText.replace( "th", RandomString ) );

Notice that we are passing in a POINTER to the function but not actually calling it. RandomString vs. RandomString(). There’s one thing I did not mention yet. Not only can you pass in a function as an argument, but when the replace method is taking place, it passes in the target match as an argument to this function. We could have re-written the function as such:

function RandomString2( strTargetInstance) // This is the target string match instance.
{
var arrLetters = ["A","B","C","D","E","V","W","X","Y","Z"];
var intLetter = (Math.floor( Math.random() * 10 ) % 9);

// Return the random letter string we get from the
// array of letters above. This time, though, we are
// going to include the target string to demonstrate
// that it has been passed in.
return( "[" + strTargetInstance + " : " + arrLetters[ intLetter ] + "]" );
}

Now, we will run it again, just once, so you can see it in action.

alert( strText.replace( "th", RandomString2 ) );

Want to read more on this? do VISIT HERE