Most efficient way to escape XML/HTML in C++ string?
Solution 1
Instead of just replacing in the original string, you can do copying with on-the-fly replacement which avoids having to move characters in the string. This will have much better complexity and cache behavior, so I'd expect a huge improvement. Or you can use boost::spirit::xml encode or http://code.google.com/p/pugixml/.
void encode(std::string& data) {
std::string buffer;
buffer.reserve(data.size());
for(size_t pos = 0; pos != data.size(); ++pos) {
switch(data[pos]) {
case '&': buffer.append("&"); break;
case '\"': buffer.append("""); break;
case '\'': buffer.append("'"); break;
case '<': buffer.append("<"); break;
case '>': buffer.append(">"); break;
default: buffer.append(&data[pos], 1); break;
}
}
data.swap(buffer);
}
EDIT: A small improvement can be achieved by using an heuristic to determine the size of the buffer. Replace the buffer.reserve
line with data.size()*1.1
(10%) or something similar depending of how much replacements are expected.
Solution 2
void escape(std::string *data)
{
using boost::algorithm::replace_all;
replace_all(*data, "&", "&");
replace_all(*data, "\"", """);
replace_all(*data, "\'", "'");
replace_all(*data, "<", "<");
replace_all(*data, ">", ">");
}
Could win the prize for least verbose?
Solution 3
My tests showed this answer gave the best performance from offered (not surprising it has the most rate).
I've implemented same algorithm for my project (I really want good performance & memory usage) - my tests showed my implementation has ~2.6-3.25 better speed performace. Also I don't like previous best offered algorithm bcs of bad memory usage - you will have extra memory usage as when apply 1.1 multiplier 'heuristic', as when .append() lead to resize.
So, leave my code here - maybe somebody find it useful.
HtmlPreprocess.h:
#ifndef _HTML_PREPROCESS_H_
#define _HTML_PREPROCESS_H_
#include <string>
class HtmlPreprocess
{
public:
HtmlPreprocess();
~HtmlPreprocess();
static void htmlspecialchars(
const std::string & in,
std::string & out
);
};
#endif // _HTML_PREPROCESS_H_
HtmlPreprocess.cpp:
#include "HtmlPreprocess.h"
HtmlPreprocess::HtmlPreprocess()
{
}
HtmlPreprocess::~HtmlPreprocess()
{
}
const unsigned char map_char_to_final_size[] =
{
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 6, 1, 1, 1, 5, 6, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 4, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
};
const unsigned char map_char_to_index[] =
{
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 2, 0xFF, 0xFF, 0xFF, 0, 1, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 4, 0xFF, 3, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF
};
void HtmlPreprocess::htmlspecialchars(
const std::string & in,
std::string & out
)
{
const char * lp_in_stored = &in[0];
size_t in_size = in.size();
const char * lp_in = lp_in_stored;
size_t final_size = 0;
for (size_t i = 0; i < in_size; i++)
final_size += map_char_to_final_size[*lp_in++];
out.resize(final_size);
lp_in = lp_in_stored;
char * lp_out = &out[0];
for (size_t i = 0; i < in_size; i++)
{
char current_char = *lp_in++;
unsigned char next_action = map_char_to_index[current_char];
switch (next_action){
case 0:
*lp_out++ = '&';
*lp_out++ = 'a';
*lp_out++ = 'm';
*lp_out++ = 'p';
*lp_out++ = ';';
break;
case 1:
*lp_out++ = '&';
*lp_out++ = 'a';
*lp_out++ = 'p';
*lp_out++ = 'o';
*lp_out++ = 's';
*lp_out++ = ';';
break;
case 2:
*lp_out++ = '&';
*lp_out++ = 'q';
*lp_out++ = 'u';
*lp_out++ = 'o';
*lp_out++ = 't';
*lp_out++ = ';';
break;
case 3:
*lp_out++ = '&';
*lp_out++ = 'g';
*lp_out++ = 't';
*lp_out++ = ';';
break;
case 4:
*lp_out++ = '&';
*lp_out++ = 'l';
*lp_out++ = 't';
*lp_out++ = ';';
break;
default:
*lp_out++ = current_char;
}
}
}
Solution 4
Here is a simple ~30 line C program that does the trick in a rather good manner. Here I am assuming that the temp_str will have allocated memory enough to have the additional escaped characters.
void toExpatEscape(char *temp_str)
{
const char cEscapeChars[6]={'&','\'','\"','>','<','\0'};
const char * const pEscapedSeqTable[] =
{
"&",
"'",
""",
">",
"<",
};
unsigned int i, j, k, nRef = 0, nEscapeCharsLen = strlen(cEscapeChars), str_len = strlen(temp_str);
int nShifts = 0;
for (i=0; i<str_len; i++)
{
for(nRef=0; nRef<nEscapeCharsLen; nRef++)
{
if(temp_str[i] == cEscapeChars[nRef])
{
if((nShifts = strlen(pEscapedSeqTable[nRef]) - 1) > 0)
{
memmove(temp_str+i+nShifts, temp_str+i, str_len-i+nShifts);
for(j=i,k=0; j<=i+nShifts,k<=nShifts; j++,k++)
temp_str[j] = pEscapedSeqTable[nRef][k];
str_len += nShifts;
}
}
}
}
temp_str[str_len] = '\0';
}
Solution 5
If you're going for processing speed, then it seems to me that the best would be to have a second string that you build as you go, copying from the first string to the second string, and then appending the html escapes as you encounter them. Since I assume that the replace method involves first a memory move, followed by a copy into the replaced position, it's going to be very slow for large strings. If you have a second string to build using .append(), it will avoid the memory move.
As far was code "cleanness", I think that's about as pretty as you're going to get. You could create an array of characters and their replacements, and then search the array, but that would probably be slower and not much cleaner anyway.
paperjam
Updated on February 28, 2020Comments
-
paperjam about 4 years
I can't believe this question hasn't been asked before. I have a string that needs to be inserted into an HTML file but it may contain special HTML characters. I want to replace these with the appropriate HTML representation.
The code below works but is pretty verbose and ugly. Performance is not critical for my application but I guess there are scalability problems here also. How can I improve this? I guess this is a job for STL algorithms or some esoteric Boost function, but the code below is the best I can come up with myself.
void escape(std::string *data) { std::string::size_type pos = 0; for (;;) { pos = data->find_first_of("\"&<>", pos); if (pos == std::string::npos) break; std::string replacement; switch ((*data)[pos]) { case '\"': replacement = """; break; case '&': replacement = "&"; break; case '<': replacement = "<"; break; case '>': replacement = ">"; break; default: ; } data->replace(pos, 1, replacement); pos += replacement.size(); }; }
-
Giovanni Funchal about 13 yearsCare for the order, you should start with "&" :-)
-
paperjam about 13 yearsTrue, unless replacements are rare. Thanks for the links too but I don't think either is practical to use.
-
paperjam about 13 yearsI didn't know about CDATA but it looks like web browsers don't respect it in HTML.
-
Giovanni Funchal about 13 yearsIf it is HTML that you want to escape, it might be much harder than simple XML. You might need a heavyweight library if you want the encoded string to be protected against weird characters. Check this: site.icu-project.org
-
paperjam about 13 yearsI'm using ASCII so surely there are only around 100 characters to consider and only a few of these might cause problems?
-
Giovanni Funchal about 13 yearsIf the input is 7 bit ascii, my function is pretty safe I think. Accents may be problematic. See this: w3.org/TR/html4/charset.html
-
Antti Huima about 13 yearsIf you just want to get the job done, definitely the most robust way to go. Encoding ASCII text HTML, though, it should be enough to quote &, < and >. You don't need to quote quotation marks if the text is not going into a node attribute.
-
Giovanni Funchal about 13 yearsThe
from
andto
strings are being passed by copy. Use aconst&
instead. Also, chainingerase
andinsert
in a loop that executesfind
is very bad for performance becausestrings
are contiguous arrays. You are potentially at O(n^3). -
vladr about 10 yearsWord of caution: the
boost::spirit::xml encode
implementation is a disaster; not only is it potentially O(N^2) from a performance standpoint, but it also fais to escape quotes (of any kind), and escapes newline/CR as\n
/\r
instead of
/
. See github.com/boostorg/spirit/blob/master/include/boost/spirit/… -
vladr about 10 yearsYour implementation should also win the prize for worst performing, as it will encode an N-long string of ampersands/quotes/etc. in O(N^2) complexity.
-
Darrin almost 9 yearsThis seems slick, and like it should work. But I get a compiler error trying to use it: std::cout << xml2::escape("<foo>bar & qux</foo>") << std::endl; error C2780: 'OutIter xml2::escape(InIter,InIter,OutIter)' : expects 3 arguments - 1 provided (Using Visual Studio 2012 Pro)
-
PatrickF almost 7 yearsWhen you use a lookup table you should use an unsigned parameter, e.g. map_char_to_index[static_cast<uint8_t>(current_char)] and not map_char_to_index[current_char].
-
SMGreenfield about 6 years@GiovanniFunchal -- I realize this is an old answered question, but what about character entities like &#xhhhh (hexidecimal XML character entity) and &#dddd (decimal XML character entity)? Should they be ignored and passed through untouched into the XML?
-
Giovanni Funchal about 6 years@SMGreenfield if your objective is escaping (as per the original question), then I believe this related question answers it stackoverflow.com/questions/1091945/…
-
Konchog almost 5 yearsThis is great - how about the inverse operation? Did you do that?
-
Sandburg over 2 yearsOverweight design and syntax. Don't go this way, it's too 90's C-stylish.