Browsed by
Author: Rodrigo Salazar

Monaco editor’s provideCompletionItems callback not firing (TriggerCharacters not working)

Monaco editor’s provideCompletionItems callback not firing (TriggerCharacters not working)

I ran into a bug where the monaco editor was not showing the autocomplete dropdown even though I had specified my trigger characters correctly.

The root cause was because of 2 issues:

  1. I did not register my custom language using monaco.languages.register(….).
  2. Once I did register my language, I was registering it after the editor was already mounted. It must be registered first.
Little-Known Awesome Algorithms: Fenwick Trees

Little-Known Awesome Algorithms: Fenwick Trees

Contrived Use Case

Imagine that we are creating an analytics tool for a financials brokerage, where orders are coming in all the time. Let’s say we’re interested in knowing how many orders fall between a certain value (a range query), in real-time. Lets say that orders can fall between $0.01 and $5M, and we want to let our clients query at any given time how many orders have gone through so far that fall between any $x and $y.

A fairly simple implementation of this would just mark down the price of each incoming order in a price array / container, and when a range query comes through we would do a simple iteration from $x to $y and sum the range together. If we want to find the range of orders that fall between $9.49 and $250 Thousand, we have to iterate from 949 pennies to 25 Million pennies (Since our data precision is to the penny), this can become a problem for some even more troublesome range queries. A solution to this is a Fenwick Tree, also known as a Binary Indexed Tree. Using this very clever data structure, we can sum the order price frequency between 949¢ and 25 million ¢ in Log time, which for a range of size 25 Million is almost nothing. Also note: Since new data is coming in all the time, a pre-calculation is not possible (unless you have a method of updating it, which this data structure happens to have as well).

The Algorithm

A Fenwick Binary Indexed Tree allows you to calculate the sum of elements in an array for any given index range in O(Log(N)) time, updates on the array are slowed from O(1) to O(Log(N)). If we chose to go with the standard ‘naive’ implementation we would have O(N) range reads and O(1) writes/updates, calculating the sum for a given index range would involve iterating over every single element in the range and adding them up.

You may be familiar with the fact that any number can be broken down into its constituent powers of two. We want to take advantage of this fact and use it to be able to represent a range by summing several ‘subfrequencies’.

We will be representing our tree in the form of an array, similar to how a heap is implemented but with a completely different indexing scheme. We want to assign each element of this array a range that it is responsible for. Lets say we are interested in finding out the cumulative frequency sum for the range 1..7, there is a very clever way of assigning range responsibilities such that we can use the position of every ’1′ in the binary representation of 7 to find out which parts of the tree are responsible for the ranges we are interested in.

Range responsibilities are assigned as follows:

  • Let ctz() represent the position of the last 1 bit in a given number, also known as ‘count trailing zeroes’. ex. ctz(12) = 2, since 12 in binary is 1100b and the last ‘set’ bit is in position 2 (from the right, 0-indexed)
  • Index i in our tree/array is responsible for the range (i – 2^ctz(i) , i]
  • Our tree array is 1-based, tree[0] does not represent anything.

Examples:

  • 7 in binary is 111b, so it is responsible for the range (110b, 111b], or (6,7]  … only itself, 7.
  • 6 in binary is 110b, so it is responsible for the range (100b, 110b], or (4, 6] … the numbers 5,6
  • 4 in binary is 100b, so it is responsible for the range (000b, 100b] or (0, 4] … the numbers 1,2,3,4
  • Notice that tree[7] + tree[6] + tree[4] = cumulative frequency sum of 1..7, and that we acquired this by continuously getting rid of the last set bit in our binary representation.

Such a responsibility tree ends up looking like this (With how the range 1..7 is interpreted):

 

vy2Ubq

 

Given this sort of tree structure here’s how we would implement finding the cumulative frequency sum between x and y. Notice we can only find ranges starting at 1, so we take the difference between 2 ranges. To find the range between 10000 and 20000 with the following code: read(20000) – read(10000).

 

int read(int idx) {
    int sum = 0;
    while (idx > 0){
        sum += tree[idx];
        idx -= (1 << ctz(idx));
    }
    return sum;
}

Note: (1 << ctz(idx)) can be greatly optimized, what we’re really doing in that line is removing the least sig figure in idx.

Updating The Tree

Remember that we still have to be able to increment certain price frequencies as they come in, so we need the ability to update this tree. Lets say an order comes in for $25.50, we want to increment the frequency of 2550 in our tree by 1. This means we need to visit every single index whose responsibility range contains 2550 and increment its value by 1 . (Or to put it in terms of the graph above, every index whose responsibility bar covers 2550.) Every index whose responsibility range contains 2550 is greater than 2550 (and 2550 itself).

We want to find the very next index greater than 2550 which whose responsibility range also contains 2550, increment its value by 1 and then repeat. Since the number 2550 is just too large to explain an example with, lets assume we’re working with the number 1. If you inspect the table below, you’ll notice that range size of a number is dependent specifically on it’s ctz() value. Also, notice the path that we follow to update the value for 1, we continue to higher values who have higher ctz, we find the next value by adding (1 << ctz(i)).

yUj2Yb

The code to update the tree is very similar to reading the tree:
Note: We stop going up the tree once we go beyond our maximum, which in our contrived example would be 5 Million dollars worth of pennies.

 

void update(int idx ,int val){
    while (idx <= MaxVal){
        tree[idx] += val;
        idx += (1 << ctz(idx));
    }
}

So that’s it, now you can read and update a Fenwick tree. Surprisingly the total lines of code is ~15.

If you found this article interesting/cool, go ahead and share or like it on your favorite social network!

Sources:
Original Research Paper
Topcoder

How to program a Gaussian Blur without using 3rd party libraries

How to program a Gaussian Blur without using 3rd party libraries

gaussian_blur

 

What is a Gaussian Blur?

Something I found fairly difficult to find online was a simple explanation on how to implement my own Gaussian Blur function. This article will explain how to implement one.

The basic idea behind a Gaussian Blur is that each pixel becomes the average of the pixels around it, sort of. Instead of simply taking the average of all the pixels around it, you take a weighted average. The weighting of each pixel is greater if it is closer to the pixel you are currently blurring. The Gaussian Blur technique simply describes how to weigh each neighboring pixel. Imagine the pixel you are currently blurring is located at the peak of the hump in the image below and the pixels around it are receiving less weight as they get farther away. You can consider the image below to be considering up to 5 pixels away, this means the Gaussian blur has a ‘window’ of size 10, also known as a kernel size.

1270790407028

 

This is where the Gaussian equation comes in, using it we can find out how much weight we want each pixel to receive and pixels receive less weight depending on its distance to the center pixel.

95ecdbb16befd4fdb760fa26c83a4b5e

Let’s explain what everything in this equation means:

σ (lowercase sigma) – This is the blurring factor, the larger this number is, the smoother/blurrier the image becomes.

e – This is simply euler’s number, a constant, 2.71828182846

x – This is the distance from the origin — The horizontal distance to the center pixel.

y – This is the distance from the origin — The vertical distance to the center pixel.

This means that x and y in this equation will be zero for the center pixel (the current pixel we want to blur), and x^2 + y^2 increases as we get farther away from the center, causing lower weights for pixels farther away.

Calculating a Gaussian Matrix, also known as a Kernel

Let’s say we wanted to find out how we would weigh neighboring pixels if we wanted a ‘window’ or ‘kernel size’ of 3 for our Gaussian blur. Of course the center pixel (the pixel we are actually blurring) will receive the most weight. Lets choose a σ of 1.5 for how blurry we want our image.

Here’s what our weight window would look like:

gaus

With each weighting evaluated it looks like this: (Notice that the weighting for the center pixel is greatest)

mat

If you’re pretty observant you’ll notice that this matrix doesn’t add up 1. For this to represent a weights, all the weights when summed together will have to add up to 1. We can multiply each number by 1/sum to ensure this is true. The sum of this matrix is 0.4787147. This means we need to multiply the matrix by 1/0.4787147 so that all elements end up adding up to 1. We finally get the following matrix which represents how we will weight each pixel during a blur.

finalans

Applying this Gaussian Kernel Matrix to an image.

Lets say this is our image: (Each number can represent a pixel color from 0-255)

image

To blur this image we need to ‘apply’ our kernel matrix to each pixel, i.e. we need to blur each pixel.

Let’s say we want to blur pixel #25 (the pixel whose color is 25 in our image matrix). This means we get pixel 25 and replace 25 with the average of its neighbors. We weigh each of the neighbors (and 25 itself) with the kernel matrix we created earlier. So it would go as follows:

stampansfinal

Now that we have weighed each neighbor appropriately, we need to add up all the values we have and replace 25 with this new value!

Loop this process with every single pixel and you will have a blurred image.

Caveats

Corner Pixels

When you need to apply this kernel matrix to a pixel in a corner, where you don’t have enough room to apply the matrix, a neat trick is to either ‘wrap around’ the image and use the pixels on the opposite side. This tends to work well if the image is intended to be tiled (typically not though) If you look at the image of the fish at the top of this article, you can tell that wrapping was used for the top row of the image since it is so dark. Another very simple solution is to just copy one of the nearest pixels into spots which are missing pixels so you can complete the process. The end result is definitely acceptable.

Time Complexity

It turns out that the simple procedure described above can be improved greatly. The time complexity of the above algorithm is O(rows*cols*kernelwidth*kernelheight). Gaussian blur has a special property called separability, the blur can be applied to each kernel row first in 1 pass, then each kernel column in another and you can achieve the same result. This means that you do not need to traverse the entire kernel matrix for each pixel. This lowers the time complexity to O(rows*cols*kernelheight + rows*cols*kernelwidth).

You can read more on the Separability property on the Gaussian Blur Wikipedia.

This was originally posted on my old blog site swageroo but has since been moved here.

Over-the-wire Natas28 Security Puzzle

Over-the-wire Natas28 Security Puzzle

You are given a search tool which finds jokes which contain your search term.

The form submission returns a 302 redirect to another page with an encrypted get param already attached. This encrypted param must contain your input in some way.

They look something like this:

G%2BglEae6W%2F1XjA7vRm21nNyEco%2Fc%2BJ2TdR0Qp8dcjPIWwm0xpPpp9XnS4%2FRG86COn7KRweZpSA6OMfSSZI8b4nOKX%2FtKRQAkZ3UXWuWWu9bzTfM5xp7c4R9mULvO1icC

The data is url encoded and base 64 encoded. Undoing those will give you the raw encrypted bytes.

ECB Mode

If you try out several different inputs you will notice a pattern. The prefix of the encrypted param does not change as your input gets longer. The first 32 bytes are always the same. This means that some text is consistently getting prepended to our text. As well, changing the first character of your input does not change the end of the encrypted text.

This indicates that the crypto mode used to encrypt this text is not using a chain block cipher, so this means that every block is independent (ECB).

Originally, I did not quite catch that this. If you mess with the encrypted text and send it to the server it will tell you that the padding is incorrect. This led me to believe that a padding oracle attack was necessary. This isn’t the case.

More Observations

The block size is 16 bytes. We can observe this by adding 1 character at a time and we can see that the third set of 16 characters stops changing once we add enough characters, it gets locked in.

We need 10 characters to fill the third block. (Adding an additional character past 10 does not change bytes in index [32:48).

Brute Forcing to Find The Appended Text

Text is being appended to the input we pass. We can tell because even if we pass exactly 10 characters to fill the third block, there’s still more blocks after that. What is the decrypted text in those blocks?

If we submit an input with only 9 characters then the last character in the third block will contain the first character of the text that is being appended to our input!

Let’s say you submit an input of 9 letter ‘a’, and you see that the value of the third block is X. Now if you try to submit an input starting with 9 letter ‘a’ and a random last character, you can compare it with X to see if you guessed correctly. Using this you can decrypt this character.

The character is a %.

Normally we would be able to extend this procedure and decrypt the entire text that is being appended. Unfortunately you will find that because the input you enter is being escaped (” turns into \”), that it is impossible to do guess and check if any of the appended characters contain characters that would be escaped and that turns out to be the case for the next character.

We can only decrypt this single % character from this procedure.

This % shows us that our text is probably being matched using a SQL LIKE. We could have inferred this instead of doing this decryption, but whatever.

SQL Injection by inserting encrypted text

We know that the structure looks like this:

SELECT text from jokes where text LIKE ‘%user_input%’;

The reason we can’t simply type in sql injection into the input box is because the app is doing sanitation of the input on the server side, all quotes are being escaped so you can not break out of the single quotes.

The escaping is being done before the encryption. This means that if we can get an encrypted block for the part of the sql query we want to inject, then we can simply insert our block and it will decrypt to the query we want.

The trick is crafting exactly the blocks we want. This is just a matter of making our input exactly the right size with padding before.

Let’s say we want to inject this (This is actually what will give us the password. I found the users table by doing another similar command):

‘  UNION ALL SELECT password FROM users;#

We want to find the exact encrypted blocks which could contain this data.

First we need to fill the third block since we know that it’s always going to already be partially filled. We know that it takes 10 characters to fill the remainder of the third block. We know that the single quote that we want in our query is going to get escaped and that’s no good. This means that we want the backslash to not be in our encrypted block.

To accomplish this, we will prepend 9 spaces to our query string so that the third block will be filled entirely before we start a fresh block for our sql injection string. Why 9? Because the single quote in our string will get escaped with a backslash and it will end up being the 10th and final character of the third block, which makes the single quote in our fourth block unescaped 🙂

This means that if we send the following string:

”         ‘  UNION ALL SELECT password FROM users;#”

We can get the encrypted blocks we want.

Ignoring the data that ends up in the third block which has our spaces and the backslash, we need the 4th, 5th, and 6th blocks which will contain our sql injection. We extract those out of the query param.

Then we do an ordinary query with a 10 character input (to fill the third block again) and just paste our encrypted blocks in right after the third block and the password is revealed.

Sample code:

import base64
import subprocess
import urllib

# For a given query string find the encrypted query param
def q(s):

s = urllib.quote_plus(s)
result = subprocess.check_output(‘curl -I -u natas28:JWwR438wkgTsNKBbcJoowyysdM82YjeF http://natas28.natas.labs.overthewire.org?query=’ + s + ‘ 2>/dev/null’, shell=True)
key = “Location: search.php/?query=”
pos = result.find(key)
pos += len(key)
start = pos
while result[pos] != ‘\n’:

pos += 1
encoded = result[start:pos]
decoded = urllib.unquote(encoded).decode(‘utf8’)

return base64.b64decode(decoded)

# Prepend 9 spaces to fill third block. The third block
# actually has room for 10 characters but the backslash
# escape character from the single quote will
# fill in the 10th remaining character in the third block!
apos = (” ” * 9) + “‘ UNION ALL SELECT password FROM users;#”

# Just a calculation to find how many blocks our encrypted
# sql injection stirng occupies
blocks = (len(apos) – 10)
while blocks % 16 != 0:

blocks = blocks + 1

blocks = blocks / 16

inject = q(apos)

# Create an ordinary query that ends the third block
# cleanly with the sql query’s single quote still open
spaces = ” ” * 10
base = q(spaces)

# Patch in our encrypted blocks that contain our sql injection
b64 = base64.b64encode(base[0:48] + inject[48:(48 + 16*blocks)] + base[48:])
url = urllib.quote_plus(b64)

# Prints a query param which gives us the password
print url

Option Delta vs Actual % In-The-Money

Option Delta vs Actual % In-The-Money

I originally posted this on medium, but have since moved it here to consolidate my blog websites.


Been playing around with options for the last few months and recently I purchased my first batch of historical CBOE options data. This is my first piece of research with the data-set.

Delta is frequently used as an approximation for the probability of an option expiring in the money (This is different from probability of profit where the underlying has to pass the strike price by the cost of the option at least). Most people understand that Delta is just an approximation for this, and there are better ways to approximate Prob-ITM but since Delta is the most frequently used it’s a good question to ask just how accurate it really is.

I wanted to see in practice how closely Delta actually tracked the true probability in the last year, specifically on the SPY.

Each trial of this experiment goes like this:

  • Choose a random instance in time in the last year (08/03/2015–07/29/2016).
  • Choose any available SPY option with 45 days of expiration or less and record it’s delta.
  • Look ahead to the future data and record whether this option expires in the money.

I repeat this trial 1 million times for call options and again 1 million times for put options.

Using deltas between 0 and 100, I bucketed the trials into aggregate buckets by placing deltas [0.5, 1.5) into bucket 1, [1.5, 2.5) into bucket 2, and so on. Then I proceeded to plot the average delta of each bucket against the observed probability of expiring in the money within my data-set’s time range.

Here is a plot for calls (the observation is that delta lower than it should be?):

1-17uexbfzcei7bmpkmainmw

Puts (the observation is that delta is higher than it should be?):

1-xgimpuizq2p85m7cr0c4ng

Once again, this is only for options in the last year on the SPY which are within 45 days of expiration. I’m not making any conclusions on this data, except that it’s not what I expected. With any piece of code written there’s always the possibility that it’s not correct or there’s a bias in some way, so take everything with a grain of salt.

Soon, I will work on plotting out probability of profit (taking into account the option price) when holding to expiration.

Feel free to comment if you have suggestions on how to improve my experiment or have any feedback.

Edit: I’ve uploaded the code and results in data form on github: https://github.com/RodSalazar/DeltaVsITMProb

Using Print Nodes within Material Shader Builder to Debug Houdini VOPs

Using Print Nodes within Material Shader Builder to Debug Houdini VOPs


Above is a video of what I’m about to explain.

If you’re working with VOP nodes to build a material shader builder then there’s a special procedure you have to follow to get the Print node working.

The Print node lets us send text to the Houdini console, but there’s extra steps necessary in this case because the material shader builder is ‘multi-context’.

The Print node has to know what context it is within before it can function, because of this it has to be piped through a Null node and connected to an output first (In the case I used in the video, a surface output).

Here are the instructions step by step:

  1. Make sure Houdini is run through the command line. If you are not running through the command line, then the Houdini console just will not appear (At least it will not appear on Windows). In the video above, I do this by making sure I open Houdini through a batch script that just opens my houdini executable. This way I just click on this file to open Houdini every time.
  2. Place a Null node in your material shader vop network. Pass the color output value as an input into the Null node, then just passthrough the color value back into the surface output node.
  3. Place a Print node and check the ‘Output text to console’ button, also insert a format string (using % will print out the first input).
  4. Attach a value you want to print as an input into the Print node.
  5. Attach the ‘text’ output of the Print node as an input into the Null node. This will make Houdini able to tell what context the Print node is running in since it will be connected to the surface output (through the Null node) at this point.
  6. Render your scene and you should see the Houdini console pop-up and print your Print node’s format string. (Make sure your material is attached to some geometry that is actually being rendered of course).

You can find information about this weird edge case on the Print VEX node documentation itself here: http://www.sidefx.com/docs/houdini/nodes/vop/print
Specifically the ‘Note’:

In a multi-context material network, the Print node needs to somehow be connected to a context output to work. The minimal way to do this is to connect a Null VOP into the context output node, and then connect the Print node’s output to the Null node’s second input.

As well, there seems to be an official answer from SideFX support here: https://www.sidefx.com/forum/topic/22087/

I spent 6+ hours trying to figure out a way to get some sort of information out of these VOPs to help debug something. A combination of this being a pretty narrow edge case and Houdini having a surprisingly small community makes this very difficult information to find.

Incorrect shadows in Houdini with the Mantra renderer, Part 2

Incorrect shadows in Houdini with the Mantra renderer, Part 2

2016-10-24_21h46_38

I originally wrote about how I had a shadow that houdini was rendering in a really bonkers way, see: http://www.s0hungry.com/2016/10/24/incorrect-shadows-in-houdini-with-the-mantra-renderer/

I have figured out what is going on, thanks to the help of a side fx engineer who commented on a post I made on the forums.

It seems like when you place down a box in houdini, by default there is a single vertex normal on each corner of the box. This is a shared vertex normal (notice that it is pointing in a direction that isn’t really normal to the flat surface).

2016-10-27_19h43_56

This means that if a shadow is going to fall on this box, the renderer will try to figure out what the surface geometry is shaped like by interpolating between these shared vertex normals. This means that the surface appears to be curved to the renderer, like a sphere.

The fix was to check off the ‘Add vertex normals’ option on the box geometry.

This gives us a result like this, where we have 1 vertex normal per vertex (All 3 at each corner).

2016-10-27_19h46_23
With this, when the surface is approximated by interpolating these vertex normals we end up with a correct result since the vertex normals are pointing in a reasonable direction (opposed to the what we have in the previous image where the vertex normal appears to be the average (?) of what these 3 vertex normals are). By doing this, we get an expected result:

2016-10-24_22h10_04

 

Incorrect shadows in Houdini with the Mantra renderer

Incorrect shadows in Houdini with the Mantra renderer

2016-10-24_21h46_38

For the past couple weeks I’ve been trying to figure out why the renders of my model had incorrectly placed shadows.

I managed to reproduce the problem with a very simple scene (The one in the above image).

There’s a spotlight pointing downwards onto a little shader ball model. The shader ball model is sitting on top of a box which I stretched out to be a floor (box from the shelf tool).

As you can see, the shadow is completely incorrect.

I have found 2 solutions to this problem. Though without understanding the implementation of the Mantra renderer, it’s difficult to say why these fix the problem.

Solution 1:

Increase the polygon count. The floor made from the box geometry immediately receives shadows rendered on it correctly once you increase ‘Axis Divisions’. By default the box from the shelf tool has 2 axis divisions. Increasing this significantly gives us a nice shadow. I can’t really consider this is a real solution since increasing the poly count of a surface just so that shadows appear on them correctly seems really bad.

Solution 2:

Add vertex normals. This seems like the best way to get this working.

2016-10-24_22h10_04

Why do either of these solutions work? Why doesn’t the Mantra renderer add these vertex normals if they’re needed for a correct render? Where is the documentation which explains this?

UPDATE, I figured this out: http://s0hungry.com/2016/10/27/incorrect-shadows-in-houdini-with-the-mantra-renderer-part-2/

 

If you have any answers, please comment or email me (rodrodsalazar@gmail.com)!

Here is the project file for the scene with the broken shadows: boxspotlight

I originally made a post about this on the Houdini forums as I was trying to find the solution for this problem: https://www.sidefx.com/forum/topic/46613/

 

How to offset, scale, rotate a material in Houdini

How to offset, scale, rotate a material in Houdini

For some reason this was an hour long ordeal to figure out to do this, mostly due to my inexperience with 3d software but also because I think the material node could be more powerful to make this easier.

After you add material to some part of your model, sometimes the texture is just too small/big or you would like it offset or rotated.

To do this you need to manipulate the texture coordinates that are attached to the area you are texturing.

Add a ‘uv texture’ node. This will add some uv vertex attributes to your model. Materials work out of the box without UVs, but adding them manually allows you to manipulate things like scale/offset/angle.

It would have been super nice if the material node itself had an option to transform uv coordinates that it receives. Allowing this would make it possible to scale/rotate/offset the default input uvs without having to drop in a UV node myself and make it easier to create things. Perhaps later I will find out a good counter argument for not having this feature, but right now it feels like a painpoint.

Bitnami