Hacker News Reader

Hacker News

Comment by danbruc | Hacker News Reader

Full thread

danbruc

In case the author sees this, some comments about Rotator.cs.

1. This algorithm will break if the number of valid characters in the BMP becomes odd.

EDIT: As user platforms pointed out, there is an unit test for this.

2. There is an overflow in line 39 because of the check i <= BMP_SIZE in line 37.

3. The web server at rot8000.com exposes at least some errors with stack traces, try rotating the string <script>.

4. In line 42 you are performing a linear search for every character you transform, that is very inefficient, especially with characters at the end of the BMP. At least use a hash map or even better just use an array mapping the input code point directly to the output code point.

5. rot8000.com does at the very least allow rather long inputs which paired with the inefficiency of the linear search makes a DoS attack pretty easy. I tried a 10,000 word lorem ipsum, it was not rejected and the request took a minute to complete.

View on HN

Thanks -- added an issue for the linear search https://github.com/rottytooth/rot8000/issues/2 -- will place a limit on chars in that textbox as well

Limiting the text box will protect you against the most naive DoS attacks, but you need some kind of limit at the API level (request size, etc.). Never trust the client.

For reference, I created an optimized implementation and tested it with a string containing all characters from U+0000 to U+FFFF in order and got the following times. The original implementation took 5202.766 ms, the optimized implementation took 0.079 ms for a speed-up of about 65858. That this is pretty close to 65536 is probably a reflection of the cost for the linear search through almost that number of characters and the test pattern I choose but I am not entirely sure, intuitively I would have expected a factor of 0.5 in there to account for the average case. But I am too lazy right now to do the math.

I've updated it to use a hashtable and the tests run quite a lot faster

I took the array approach which should be still faster because it avoids the hash calculations. Just build an array Char[65536] containing at every index i the character the character i should be mapped to. Rotator.Rotate() then simply becomes the following where Rotator.map is the precomputed array. Probably very similar to an implementation using a hash table. I also got rid of the string builder but did not profile the difference. If one uses a string builder it would most likely help to specify the capacity in the constructor call so that the internal array does not have to be resized repeatedly as the result is constructed and grows in length.

  public static String Rotate(String input)
  {
    var result = new Char[input.Length];

    for (var index = 0; index < input.Length; index++)
    {
      result[index] = Rotator.map[input[index]];
    }

    return new String(result);
  }

not a js guy - any reason this needs any lookup table at all?

quick googling seems to suggest simple bitshifting could be possible..

Because the basic multilingual plane that it operates on isn't actually full.

Reply on news.ycombinator.com