2
\$\begingroup\$

I quickly wrote a short program to split a string into \$n\$ lengths with variable-character padding:

#include <iostream>
#include <algorithm>

std::string getString();
int getBlockSize();
char getPaddingChar();
std::string addPadding(std::string str, int blockSize, char paddingChar);
std::string tokenize(std::string str, int blockSize);

int main(){
    std::string str = getString();
    int blockSize = getBlockSize();
    char paddingChar = getPaddingChar();

    str.erase(std::remove(str.begin(), str.end(), ' '), str.end());
    str = addPadding(str, blockSize, paddingChar);
    str = tokenize(str, blockSize);

    std::cout << str;

    std::cout << '\n';
    return 0;
}

std::string getString(){
    std::cout << "Input string: ";

    std::string str;
    std::getline(std::cin, str);

    return str;
}

int getBlockSize(){
    std::string inputStr;
    int blockSize;

    do{
        try{
            std::cout << "Block size: ";
            std::getline(std::cin, inputStr);
            blockSize = std::stoi(inputStr);
        } catch(...){
            blockSize = 0;
        }
    } while(blockSize < 1);

    return blockSize;
}

char getPaddingChar(){
    char paddingChar;

    do{
        std::cout << "Padding character: ";
        std::cin >> paddingChar;
        std::cin.ignore(std::numeric_limits<std::streamsize>::max(),'\n');
    } while(std::cin.fail());

    return paddingChar;
}

std::string addPadding(std::string str, int blockSize, char paddingChar){
    while(str.length() % blockSize != 0){
        str += paddingChar;
    }
    return str;
}

std::string tokenize(std::string str, int blockSize){
    for(int i = blockSize; i < str.length(); i += blockSize+1){     
        str.insert(i, 1, ' ');
    }
    return str;
}

This code firstly gets the input string (str), gets the size of the block (blockSize), and then gets the character that is to be used as padding (paddingChar).

It then removes all spaces from input string, adds padding, and then tokenizes the string by splitting it into blockSize pieces.

Example output:

Input string: Tis' but a scratch!
Block size: 11
Padding character: X
Tis'butascr atch!XXXXXX

The splitting of a stream of characters into blocks is common in cryptography. While there certainly are many, many Code Review questions on tokenization, I was unable to find one that was exactly like this and in C++, so I felt that this area should also be covered in that aspect.

I tried to use the helpful suggestions from my previous Code Review questions to improve the quality of my code as best I could. Despite that, there is always room to improve the way that I write code.

How can I improve this code?

\$\endgroup\$
  • \$\begingroup\$ isn't this algorithm lossy? i.e. how do you recover the original plaintext? \$\endgroup\$ – Richard Hodges Jan 16 '17 at 11:45
  • \$\begingroup\$ @RichardHodges The message is still decipherable by a human, i.e. you can still tell that the message Tis'butascr atch!XXXXXX is meaning Tis' but a scratch!. This type of classical cryptography is mainly used as a first step before something like columnar transposition. But you're right, it isn't meant for a computer to recover the plaintext, that would be much harder. \$\endgroup\$ – esote Jan 16 '17 at 16:53
2
\$\begingroup\$

My first impression is that we would probably wish to avoid copying and shuffle data as much as possible.

The code as presented does the following:

  1. conditionally remove items (worst case time complexity occurs when every char is a space, in which case it's \$\mathcal{O}(\frac{n^2}{2})\$ (more or less))

  2. append padding (worst case will involve a reallocation plus copy \$\mathcal{O}(n)\$)

I think we can do better, performing the entire operation in linear time and guaranteeing no memory reallocations. This involves iteratively conditionally copying the bytes. We can do this because std::string's iterators are random-access, so we can compute distances in constant time.

I have presented it here as a simple composition of methods in a lightweight engine object. Another way would be to create a state machine which could be chained to another encryption stage:

#include <iostream>
#include <algorithm>

struct squish_engine
{
    squish_engine(std::size_t blockSize, char paddingChar)
            : blockSize(blockSize)
            , paddingChar(paddingChar)
    {

    }

    // useful for initial allocation of destination string
    std::size_t estimate_size(std::size_t plaintext_length) const {
        return plaintext_length + blockSize;
    }

    // a predicate    
    static bool matchesSpace(char c) {
        return c == ' ';
    }

    // operation in terms of iterators    
    template<class FromIter, class ToIter>
    ToIter operator()(FromIter first, FromIter last, ToIter first2) const
    {
        // use stl algorithms where possible
        auto last2 = std::remove_copy_if(first, last, first2, matchesSpace);
        auto pads = std::distance(first2, last2) % blockSize;
        if (pads) {
            pads = blockSize - pads;
        }
        last2 += pads;
        return last2;
    };

    // this is the public interface    
    template<class Iter>
    std::string operator()(Iter first, Iter last) const
    {
        // build an overly-large string to accept the result.
        // we may as well pad it now, as it's no extra cost compared
        // to zero-filling
        std::string result(estimate_size(std::distance(first, last)), paddingChar);
        // our internal operator will compute the end point of the
        // padded area for us
        auto last2 = (*this)(first, last, std::begin(result));

        // so we can simply truncate any padding chars we don't need
        result.erase(last2, result.end());

        // and return the cypher
        return result;
    }

    // convenience interface
    std::string operator()(const std::string& s)
    {
        return (*this)(std::begin(s), std::end(s));
    }

    std::size_t blockSize;
    char paddingChar;
};

// the concept of making a copy while filtering
template<class Filter>
std::string filter_copy(const std::string& source, Filter&& filter)
{
    return filter(source);
}

int main(){

    std::size_t blockSize = 11;
    char paddingChar = 'X';

    std::string str = "Tis' but a scratch!";

    // now we can conceivably choose the encryption engine at the
    // client call site
    auto compressed = filter_copy(str, squish_engine(blockSize, paddingChar));

    std::cout << compressed << '\n';
    return 0;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.