Arrrrrrrrg!
As I said, I have made a nice new decimal maths library and am using it in one of my bits of code.
It was a simple update. The original code evaluated a simple sum and provided an answer. It was a tad quick and cheerful (a bit of a bodge) but worked well enough until recently. The new code does the same but using my new library.
What could go wrong - it was a function to evaluate a text decimal sum, simple as that. How hard could it be?
The original function just added and subtracted. It worked out how many decimal places were in play and did integer maths to that precision and printed result to that many places. I said it was a bodge.
This meant, as a fluke of the way it worked, 1.00+2 would be 3.00. I.e. the number of places in the output was dependant on the max number of places of the arguments. This was never a documented feature, but guess what, people were assuming it would work like that. This is in spite of output formatting for money to two places which is what I was using in my stuff.
Then we get the fact the old code allowed blanks for operands and treated as 0. Again, a fluke of the original code and not a documented feature, but once again, they were relying on it.
It is infuriating having to make special cases in code to reproduce old and totally undocumented side effects in some function just to keep users happy! I suspect that even if the manual had said "You cannot assume a specific number of decimal places in the output" and "Behaviour for an input that is not a well formed numeric expression is undefined and cannot be relied on" it would not be any different. Users are like that!
I am waiting for the next thing, but I have a feeling it is a side effect of the total lack of error handling and syntax checking in the earlier bodged code. I might end up refusing to fix what happens when total garbage is thrown at the function and insist they fix their use cases. We'll see how bad it is.
Arrrrrrrrrrrrg!
Showing posts with label CODING. Show all posts
Showing posts with label CODING. Show all posts
2020-03-09
2019-01-04
Maze complexity
Making a maze is relatively simple, or so you would think. In this case the maze only has one path to get from start to end, and no loops, and all squares are occupied.
Firstly I have to consider what makes the maze "hard" or "easy", and I did a lot on this when I coded the first version of my maze back in 2017. In that case I created random mazes and "scored" them, including factors like how many dead-ends there were. I picked one with a good score.
The issue is that some of the factors are not obvious. E.g. a good factor is how long the solution path is - longer the better, or so you would think. The problem is that the longer the path is, the fewer "squares" on the maze are occupied with dead-ends. The longest path has no dead ends so whilst it takes a while, the maze is ultimately very easy as you cannot take any wrong turns.
Similarly if the path is too short, e.g. straight line from start to end, it is far too easy to find the solution, especially if you can see the maze. So there is a compromise.
The number of dead-ends is also not an ideal metric - you want dead-ends, but they need to be long enough not to be obvious as dead-ends, especially if you can see the maze.
The simple algorithm
The basic algorithm I have used to make mazes in the past is one where we have a current point on the maze (you can start anywhere as ultimately every square is used, and so it will always create a path from any arbitrary start point to any arbitrary end point). You consider the options of moving to an adjacent vacant square, and pick one at random, drawing the maze to that next point. When you find you cannot move you back track until you can. Ultimately you back track to the start and the maze is full.
A minor enhancement is to bias the directional choice. E.g. starting at bottom of maze a bias to go back down can create a maze that has more ups and downs than just random. Similarly, with a wrapped maze (as we have here) a bias to left and right can create long horizontal paths which are fun.
Another minor enhancement is to pick the exit point at the longest path, if that is an option.
However, the algorithm as a whole as a major flaw - because, when you reach a dead-end, you back track until you can move, you are making dead-ends as short as possible. You always back-track as little as possible. The result is a path from start to end which has lots of short and obvious dead ends.
A simple fix
A very simple enhancement was to start two paths in parallel from the start point of solving the maze. This allows two long paths to exist and creates a "wrong direction" from square one, which is not obvious. The trick of picking the longest point for exit helps ensure the longest of these paths is the solution.
A more complex algorithm
I have now come up with a more complex algorithm. This works by having a set (queue) of points, each of which looks at the adjacent empty squares and picks a direction (as before), but the new point is added to the end of the queue of points to consider next. This means the maze spreads out like a tree from the start point. The trick of picking the longest point for exit helps ensure the longest of these branches is the solution.
This does not work in itself, as you create a maze that is way too simple - far too many paths at once means that they have no choice where to go and hence have to be simple. Even picking the direction randomly, the results are all stupidly simple.
When adding the next point to the queue, I can add to the start of the queue (for immediate consideration) or to the end of the queue (considering all other points in the queue first). If added to the start, then it makes for a long path that can travel unimpeded around empty space before the other paths are tried. If added to the end, then the other paths are handle in parallel with the above result. The same decision applies to the current point considering other directions it could take.
This creates an opportunity for a parameter - one that controls a random chance of adding to start or end. I have added this as a maze-complexity setting.
By allowing a bias as to which end of the queue is used, it creates a range of maze complexities. However, even at one extreme, always adding the next point to the start so it can continue (much like the original algorithm) the key difference is what happens when a dead end is reached - in this case the alternative path is the earliest added to the end of the queue, i.e. the longest "back-track" we can do. This alone makes for more complex mazes.
Of course if you push it too far towards short dead-ends you get some very odd mazes...
Needless to say, this makes for more challenging maze puzzles now.
Firstly I have to consider what makes the maze "hard" or "easy", and I did a lot on this when I coded the first version of my maze back in 2017. In that case I created random mazes and "scored" them, including factors like how many dead-ends there were. I picked one with a good score.
The issue is that some of the factors are not obvious. E.g. a good factor is how long the solution path is - longer the better, or so you would think. The problem is that the longer the path is, the fewer "squares" on the maze are occupied with dead-ends. The longest path has no dead ends so whilst it takes a while, the maze is ultimately very easy as you cannot take any wrong turns.
Similarly if the path is too short, e.g. straight line from start to end, it is far too easy to find the solution, especially if you can see the maze. So there is a compromise.
The number of dead-ends is also not an ideal metric - you want dead-ends, but they need to be long enough not to be obvious as dead-ends, especially if you can see the maze.
The simple algorithm
The basic algorithm I have used to make mazes in the past is one where we have a current point on the maze (you can start anywhere as ultimately every square is used, and so it will always create a path from any arbitrary start point to any arbitrary end point). You consider the options of moving to an adjacent vacant square, and pick one at random, drawing the maze to that next point. When you find you cannot move you back track until you can. Ultimately you back track to the start and the maze is full.
A minor enhancement is to bias the directional choice. E.g. starting at bottom of maze a bias to go back down can create a maze that has more ups and downs than just random. Similarly, with a wrapped maze (as we have here) a bias to left and right can create long horizontal paths which are fun.
Another minor enhancement is to pick the exit point at the longest path, if that is an option.
However, the algorithm as a whole as a major flaw - because, when you reach a dead-end, you back track until you can move, you are making dead-ends as short as possible. You always back-track as little as possible. The result is a path from start to end which has lots of short and obvious dead ends.
A simple fix
A very simple enhancement was to start two paths in parallel from the start point of solving the maze. This allows two long paths to exist and creates a "wrong direction" from square one, which is not obvious. The trick of picking the longest point for exit helps ensure the longest of these paths is the solution.
A more complex algorithm
I have now come up with a more complex algorithm. This works by having a set (queue) of points, each of which looks at the adjacent empty squares and picks a direction (as before), but the new point is added to the end of the queue of points to consider next. This means the maze spreads out like a tree from the start point. The trick of picking the longest point for exit helps ensure the longest of these branches is the solution.
This does not work in itself, as you create a maze that is way too simple - far too many paths at once means that they have no choice where to go and hence have to be simple. Even picking the direction randomly, the results are all stupidly simple.
When adding the next point to the queue, I can add to the start of the queue (for immediate consideration) or to the end of the queue (considering all other points in the queue first). If added to the start, then it makes for a long path that can travel unimpeded around empty space before the other paths are tried. If added to the end, then the other paths are handle in parallel with the above result. The same decision applies to the current point considering other directions it could take.
This creates an opportunity for a parameter - one that controls a random chance of adding to start or end. I have added this as a maze-complexity setting.
By allowing a bias as to which end of the queue is used, it creates a range of maze complexities. However, even at one extreme, always adding the next point to the start so it can continue (much like the original algorithm) the key difference is what happens when a dead end is reached - in this case the alternative path is the earliest added to the end of the queue, i.e. the longest "back-track" we can do. This alone makes for more complex mazes.
Of course if you push it too far towards short dead-ends you get some very odd mazes...
Needless to say, this makes for more challenging maze puzzles now.
2018-04-27
Security is fun
I say "for a change", but we have people that help with testing these early releases all the time. However, the ACME code has really been very popular and people want to test it. The whole project has been fun for us too.
The good news is that for most testers the ACME system has "just worked" - they set up DNS for a hostname for the public IP of their FireBrick, put in the config, and within seconds they have a certificate for HTTPS and IPsec. Indeed, so simple and so fast, people are already asking if any way for FireBrick to do the ACME as a front for other servers?!? I thought apache made this easy, but apparently FireBrick is easier, according to customers. That is, perhaps, a good sign!
What is also fun is the number of ways people find to break it!!!
This is one of those cases where we will be making alphas with minor tweaks for a week or two I am sure. Some of the challenges have been surprising, although all, so far, have been minor.
We have people running networks that only work over IPv6, which is good. But then we have people doing that only over 6over4 tunnels, which causes some challenges with source IPv6 addresses.
We have had a few cases with firewall issues. The logic on the FireBrick is that the brick itself should not need a firewall. The individual services have, at the initial packet level, controls on IP access ("allow" lists, and "local-only" settings). Indeed, some versions of FB600 have no "firewall" as such, and only use these access controls. This is important for the ACME logic as the brick needs to be accessible via HTTP on port 80 from Let's Encrypt (or chosen CA) to authenticate the domain. The code allows port 80 access even when otherwise locked down so as to establish TCP and send an HTTP request for the specific ACME authentication URL. This means port 80 open for a few seconds every couple of months but only for that specific URL and no other access (unless allowed anyway). That does not work if firewall rules (on the FireBrick, or externally) stop that access.
We are also looking at what controls we need. For example, the FireBrick obtains new key pairs as needed (and we need at least two for ACME) from a FireBrick server (see P.S. below). But best practice is to create your own private keys on an isolated laptop and install via a direct connection to the FireBrick. That is hard work for most so we have a convenient and secure way to get from us over TLS (trusting us), but for good security reasons we need config settings to prevent that if the end users wants it locked down. We have that (acme-keygen) for those that need it.
We also load some root CA certificates so we can access Let's Encrypt servers and check them, but again we may need some controls so people can decide what CA certificates they have installed. So there are likely to be some changes to control that soon.
This is a key example of the fact that security is a compromise with convenience, and sometimes the convenience is important as without it people won't bother with the security. So a lot of what we are doing is a fine line - make it so people can, and will, use https with proper certificates, but that means some levels of trusting us as well. And we have to allow for the fine-tuning that some people may want to decide which side of that fine line they wish to work.
So it is a fun bit of code, not just at the "nuts and bolts" level as per my last blog post but at the high level of considering attack vectors and risk and trust.
I am sure more issues will come to light over there next week or two - so do try the alpha, and let us know any issues you have.
P.S. After a lot more research, we feel confident enough to have the key generation done locally in the FireBrick, which is obviously better. It means first time of ACME will take longer, obviously, as we need to collect entropy and generate keys. Obviously you can still load your own keys instead.
2018-03-15
memcpy
Having been caught out by this (and yes, I should know better) this is a friendly reminder for those coding in C.
The man page on memcpy is clear.
In days gone by the memcpy would be done by a simple loop copying bytes from src to dst until length runs out. e.g. while(len--)*dst++=*src++; or some such, but probably in assembler.
So a classic case of copying a block of data back a few bytes, e.g. memcpy(data,data+1,len) would be fine.
Unfortunately the warning of The memory areas must not overlap. is not to be ignored.
You will get away with ignoring it a lot, and that is the problem! Whether you get away with it depends on a lot of things. Version of C libraries and even version of the compiler, the specific alignment of the points you are moving data to and from, the length you are moving, and probably more factors I cannot think of.
So things may work 100% until next recompiled, or simply until run on a new machine. Worse, they may work most of the time, but not quite all.
The reason is that a memcpy can be carefully optimised. For example, on an ARM you can load a whole load of registers in one go and then store a whole load of registers in one go. It may be more optimal for it to start copying from the end and work backwards, for example. The specification of memcpy not permitting overlapping areas allows for all number of optimisations to be performed in the implementation.
On the other hand memmove has to allow for overlapping areas.
In practice it does not have to copy to somewhere temporarily, just make sure it moves data in the right order if there is an overlap. This means more checks and code that may not have quite the same optimisations available.
So, always be careful to use memmove if you cannot be sure the memory areas do not overlap.
P.S. Someone pointed out I am getting forgetful. See http://www.revk.uk/2011/02/memcpy-minor-duh-moment-on-my-part-and.html
The man page on memcpy is clear.
DESCRIPTION
The memcpy() function copies n bytes from memory area src to memory area dest. The memory areas must not overlap. Use memmove(3) if the memory areas do overlap.
In days gone by the memcpy would be done by a simple loop copying bytes from src to dst until length runs out. e.g. while(len--)*dst++=*src++; or some such, but probably in assembler.
So a classic case of copying a block of data back a few bytes, e.g. memcpy(data,data+1,len) would be fine.
Unfortunately the warning of The memory areas must not overlap. is not to be ignored.
You will get away with ignoring it a lot, and that is the problem! Whether you get away with it depends on a lot of things. Version of C libraries and even version of the compiler, the specific alignment of the points you are moving data to and from, the length you are moving, and probably more factors I cannot think of.
So things may work 100% until next recompiled, or simply until run on a new machine. Worse, they may work most of the time, but not quite all.
The reason is that a memcpy can be carefully optimised. For example, on an ARM you can load a whole load of registers in one go and then store a whole load of registers in one go. It may be more optimal for it to start copying from the end and work backwards, for example. The specification of memcpy not permitting overlapping areas allows for all number of optimisations to be performed in the implementation.
On the other hand memmove has to allow for overlapping areas.
DESCRIPTION
The memmove() function copies n bytes from memory area src to memory area dest. The memory areas may overlap: copying takes place as though the bytes in src are first copied into a temporary array that does not overlap src or dest, and the bytes are then copied from the temporary array to dest.
So, always be careful to use memmove if you cannot be sure the memory areas do not overlap.
P.S. Someone pointed out I am getting forgetful. See http://www.revk.uk/2011/02/memcpy-minor-duh-moment-on-my-part-and.html
2018-02-16
Apple iMac Pro 10G Ethernet buggy?
I would be interested in anyone else able to test this on their iMac Pro to confirm as it seems highly unlikely to be anything but a simple driver bug. Sadly to test you need to craft broken TCP/IP packets.
Myself and a colleague have wasted a lot of time trying to track an issue over the last few days, it seemed to be that a simple TCP stream could have corrupted data in it.
Basically, we would do a test of a web page served from a device (the FireBrick as it happens, with test s/w on it), and the page would be all nulls and spaces, or should be, but random corruption would appear.
To be 100% frank we have not tracked it down yet, but we initially assumed it had to be an issue in the new FireBrick code. We are just launching the FB2900, so any issue in testing is somewhat serious.
Now, if you know anything about networking, TCP as a stream will only work if you get proper packets at both the TCP level and lower levels like Ethernet, with good checksums/CRCs. Whilst Ethernet is generated on each link. The TCP checksum is end to end (no NAT involved here).
So, you have a visible, albeit slightly intermittent problem - basically view a specific web page from a specific device and see gibberish in the page. You naturally assume it has to be within the TCP stack / processing of each end as that is where data could be corrupted without breaking the TCP checksum logic. There are two ends, one is my nice shiny new iMac Pro and the other is a FireBrick somewhere on the end of a DSL line. It has to be one of those two ends with the issue, and well, obviously not the iMac, so look at the newest code, and latest hardware, at the FireBrick end. Anywhere in between would cause a TCP checksum error and so we would not see in the final TCP stream.
A lot of time wasted, and a clue pops up - cannot make it happen from the iMac (not the Pro) at the office. Hmmm. Sadly it is a tad intermittent, so not conclusive. I could not make it happen locally either, but assumed the slower uplink and more buffering may be a factor.
Then it gets really really weird, and I can imagine some network engineers would pull their hair out at this point. On my home iMac Pro I did lots of the same test. I tested on wired Ethernet (running only at 1Gb/s), and on WiFi. Every time on wired it got corruption. Every time on WiFi it did not. A dozen tests. Pretty conclusive. WTF?
Seriously how can that be - clearly the iMac Pro is not randomly corrupting TCP streams, as I would notice in web pages, images, etc. Even, as it seems, levels like 1 in 1000 packets, you'd notice. So why only the stream from the FireBrick. It cannot just be an iMac bug...
So I used wireshark to pcap on the iMac Pro, and yes, it saw the corrupted content. Odd. Then it occurred to me - tell wireshark to check checksums. Bingo, the TCP checksum is bad. Yet the iMac Pro has accepted the packet and fed the corrupted data in to the TCP stream!
This changes the game massively. It means this is a raw data corruption somewhere on the route from the FireBrick to me. It could be ANYTHING now, as not in the TCP realm as the TCP checksum is wrong. We were (probably) looking in totally the wrong place for this issue. Thanks Apple!
It seems that the iMac Pro wired Ethernet is not checking TCP checksums. The WiFi is fine. Likely cause is that they use h/w TCP checksum logic on the MAC (not Mac, I mean Media Access Control, the Ethernet hardware) and there is either a h/w or s/w bug meaning the checksum check is not being checked! It is an easy bug to exist and one you will not notice generally as almost all packets have no TCP level corruption!
Reported to Apple but also said that I am not spending ages doing logs and crap for them unless I am paid my hourly rate.
When debugging you really do not expect two unrelated bugs to be in play at once. This is hard work.
Sadly, at this point, we confirmed the corruption is definitely upstream of my Mac (dumps on router in-between), but the bug has vanished for now - Heisenbugs we call them. If/when we manage to reproduce it, we can then trace at each step along to way to find if an issue in our network, BT, the modem, switches, and so on, or, as is seemingly increasingly unlikely, the FireBrick at the far end. As this happened on old FB2700 and new FB2900 on this DSL line, but not anywhere else, the chance of this being in the FireBrick is getting vanishingly small.
Chasing bugs can be hard!
P.S. looks like it was BT supplied VDSL modem all along. Wow.
Myself and a colleague have wasted a lot of time trying to track an issue over the last few days, it seemed to be that a simple TCP stream could have corrupted data in it.
Basically, we would do a test of a web page served from a device (the FireBrick as it happens, with test s/w on it), and the page would be all nulls and spaces, or should be, but random corruption would appear.
To be 100% frank we have not tracked it down yet, but we initially assumed it had to be an issue in the new FireBrick code. We are just launching the FB2900, so any issue in testing is somewhat serious.
Now, if you know anything about networking, TCP as a stream will only work if you get proper packets at both the TCP level and lower levels like Ethernet, with good checksums/CRCs. Whilst Ethernet is generated on each link. The TCP checksum is end to end (no NAT involved here).
So, you have a visible, albeit slightly intermittent problem - basically view a specific web page from a specific device and see gibberish in the page. You naturally assume it has to be within the TCP stack / processing of each end as that is where data could be corrupted without breaking the TCP checksum logic. There are two ends, one is my nice shiny new iMac Pro and the other is a FireBrick somewhere on the end of a DSL line. It has to be one of those two ends with the issue, and well, obviously not the iMac, so look at the newest code, and latest hardware, at the FireBrick end. Anywhere in between would cause a TCP checksum error and so we would not see in the final TCP stream.
A lot of time wasted, and a clue pops up - cannot make it happen from the iMac (not the Pro) at the office. Hmmm. Sadly it is a tad intermittent, so not conclusive. I could not make it happen locally either, but assumed the slower uplink and more buffering may be a factor.
Then it gets really really weird, and I can imagine some network engineers would pull their hair out at this point. On my home iMac Pro I did lots of the same test. I tested on wired Ethernet (running only at 1Gb/s), and on WiFi. Every time on wired it got corruption. Every time on WiFi it did not. A dozen tests. Pretty conclusive. WTF?
Seriously how can that be - clearly the iMac Pro is not randomly corrupting TCP streams, as I would notice in web pages, images, etc. Even, as it seems, levels like 1 in 1000 packets, you'd notice. So why only the stream from the FireBrick. It cannot just be an iMac bug...
So I used wireshark to pcap on the iMac Pro, and yes, it saw the corrupted content. Odd. Then it occurred to me - tell wireshark to check checksums. Bingo, the TCP checksum is bad. Yet the iMac Pro has accepted the packet and fed the corrupted data in to the TCP stream!
This changes the game massively. It means this is a raw data corruption somewhere on the route from the FireBrick to me. It could be ANYTHING now, as not in the TCP realm as the TCP checksum is wrong. We were (probably) looking in totally the wrong place for this issue. Thanks Apple!
It seems that the iMac Pro wired Ethernet is not checking TCP checksums. The WiFi is fine. Likely cause is that they use h/w TCP checksum logic on the MAC (not Mac, I mean Media Access Control, the Ethernet hardware) and there is either a h/w or s/w bug meaning the checksum check is not being checked! It is an easy bug to exist and one you will not notice generally as almost all packets have no TCP level corruption!
Reported to Apple but also said that I am not spending ages doing logs and crap for them unless I am paid my hourly rate.
When debugging you really do not expect two unrelated bugs to be in play at once. This is hard work.
Sadly, at this point, we confirmed the corruption is definitely upstream of my Mac (dumps on router in-between), but the bug has vanished for now - Heisenbugs we call them. If/when we manage to reproduce it, we can then trace at each step along to way to find if an issue in our network, BT, the modem, switches, and so on, or, as is seemingly increasingly unlikely, the FireBrick at the far end. As this happened on old FB2700 and new FB2900 on this DSL line, but not anywhere else, the chance of this being in the FireBrick is getting vanishingly small.
Chasing bugs can be hard!
P.S. looks like it was BT supplied VDSL modem all along. Wow.
2017-11-29
Tracing a bitmap
To me, this seems very obvious, but it is interesting that people do have different algorithms for doing this. So I thought it worth documenting how I did it.
The objective is to make an SVG, which uses a path to draw around something and fill it with a colour, from a bitmap. A bitmap has each pixel that is a colour on a grid. It is very obvious how a bitmap works when looking at the QR code as it is clearly made of squares of black and white.
Simplistic
This obvious and simplistic approach is make an SVG rectangle for each pixel. That makes for a large SVG file, hence the idea of tracing around multiple pixels of the same colour and using a path.
Not just black and white
The first thing I considered was that this could be more generic than just black and white. We already use an image library to generate a bitmap using indexed colours. This means we have a grid of bytes, each of which has a value 0 to 255, each representing one colour. A separate table says which colour is actually used for each number. It is a paint by numbers system.
I already use this to generate the existing PNG images, including the QR code. But why not make the tracing function a generic SVG output for any indexed bitmap we make.
This basically means tracing each colour, one after the other. However, the principle is just the same for black and white images.
Background colour
Even with an indexed colour bitmap there is often the notion of a background colour. So my code starts by checking if one has been specified and making a simple rectangle of that colour for the whole bitmap.
With the QR code this is simple, it is white. Not a lot of people know that QR codes actually require 3 pixels of white all the way around. You often see them with one pixel, or even in some cases with none (krispy kremes boxes?).
Sometimes the background colour is also transparent in which case you don't plot it at all. Obviously a simple check to see if any pixels are the background colour, and if none, then don't bother either.
In any case, if there is a background, you don't include that colour in the tracing as it is already handled.
Just black
Obviously for the QR code it is simple. The indexed colours are just 0 (white) and 1 (black), with 0 as the background colour. So we do a white rectangle, and then a path for the black. Where there are multiple colours we just trace each (non background) colour one at a time.
Directions
As part of the walking around the image tracing it, we have to consider facing a direction. Imagine you are standing on a square on a chess board, you can be facing one of 4 ways, to consider the 4 sides of the square on which you stand...
When working on a direction, some times we have to add or subtract, and we do so using modulo arithmetic, so adding 1 to 3 becomes 0. As such adding 1 is turning right and subtracting 1 is turning left.
In the code, a simple dx and dy table can be used to hold the offset for each direction.
Repetition
As we scan the image to find areas to trace around, we could easily find we are going over the same thing more than once. To avoid this we also create a byte array, one per pixel, in which we record the edge of that pixel which we have already traced. This is one bit per direction so actually only 4 bits used in each byte. This stops us accidentally trying to trace any edge of any pixel more than once. We only record the edge of the pixel we are in, not the other side, i.e. the opposite edge on the adjacent pixel, as that will be recorded when we trace its colour. Obviously if the other colour is the background, as with out QR codes, then that does not get traced, but if it was in fact another colour to trace, we don't want to record that edge as having been traced yet.
Over the edge
Obviously, as part of this, we need to look at the colour of a pixel, so we make a function that takes an x and y co-ordinate and returns the colour. The indexed colours are 0 to 255. However, we allow full integers for x, y, and the result. This means we can look over the edge of the bitmap, either negative x, or y, or values beyond the width and height of the image, and these can return -1 for the colour which will match no colour actually in the image.
What this means is we can look at the pixel in any direction and see that it is a different colour, so it is the edge of what we are tracing. We do not have to have a special case for looking in direction 3 when on the left of the image, we simply see that as colour -1, so clearly the edge of what we are tracing.
Finding areas to trace
The first thing to do is scan the image for the colour we are tracing. Remember, we are tracing one colour at a time, and not bothering to trace the background colour at all. For QR codes, that means we only trace black.
- We scan from top to bottom and left to right in a simple loop looking first for a pixel of the colour we are tracing.
- We then consider what edge of that pixel we want to trace, looking in turn at direction 0, 1, 2, 3 and looking for a pixel in that direction which is not the same colour, so an edge of the block of pixels of this colour. We also disregard any directions where we have already done that edge of this pixel.
- If we find no directions that match that rule, then this is not a pixel to trace. It is either one we have done already, or one that is surrounded by pixels of the same colour so does not need tracing.
- If we do find a direction, then that is our starting point for walking around a set of pixels of this colour, doing the trace.
Actually, it is slightly simpler! I said we check 0, 1, 2 and 3 to find an edge to trace, but in practice we can only see 0 or 2.
It may seem obvious actually that you should only ever see 0. After all, the pixel above must be a different colour. If it is the same colour then we already did it, and so the whole block of pixels we are in has already been traced, and so if direction 0 is the same colour, any edge on 1, 2, or 3 must have been traced as part of that block, surely.
Well, actually no, there is an edge case (:-) if the block of pixels we have already traced, i.e. direction 0 is the same colour, but it fully encompasses pixels of a different colour.
Whilst the outside of this black block has been traced, this is an edge to an interior area, and so has not been, and it is direction 2.
So why could we not have direction 1 or 3? Well if it was 1, that means the interior area in question would have been found one row further up already with a black pixel facing down (direction 2) already. Similarly, if the interior pixel was on the left (direction 3) it would have been seen facing down (direction 2) from a previous row.
So actually there are only two possible ways would could be facing to start, 0 and 2. Not that it matters, but 0 is exterior and 2 is interior.
Doing the trace
Having found a starting point, you then do the trace. The direction you are facing is the edge you are going to draw, for each edge you only need to plot one point, and you make up a set of points that are going to be a closed filled area. In SVG you use M x y for the start and L x y for a line, so you need a flag to know you are doing the first point and use the M.
But which point is it? You are looking at an edge, and it does not really matter if you pick the left or right point on that edge in the direction you are facing, as long as you are consistent. In this example I pick the one on the right (considering the direction I am facing).
You mark this edge has having been done in your byte array of edges. And you add this point to the list of points for this trace.
You then move on, and this is where you have to walk around the area you are tracing. So we have to make a decision.
There are three possible choices of how you move...
Firstly, can you turn left around a corner? This means moving to a pixel that is one space right from the direction you are facing (d+1), and then one place left of that (d). To decide if you can move there you simple check if that pixel is the same colour. If so, then move there, and also turn left (d-1). This leaves you facing the same pixel you started facing, so you know it is a different colour already and so don't have to check.
If you can't do that, you may be able to move right. This is only if you cannot do the above move. To do this you simply check if the pixel to your right (d+1) is the same colour. If it is, you move there, but do not change your direction (d). You end up facing the pixel you could not move to in the above case, so again, you know you are facing a pixel of a different colour still.
Finally, if that does not work, you simply turn right, this means staying in the same place by changing to (d+1) direction. Again, this leaves you facing the pixel you could not move to in the above case, so again, you know you are facing a pixel of a different colour still.
When to stop
You keep going, adding a new point, and marking an edge as done, until you find you are facing an edge that is already done. That means you have got back to the start. Then you move on to the next pixel in your scanning to find the next area to trace.
Closing the path
This does not actually result in plotting the end point, as you stop when you get back to the start, but that is fine as the SVG full does not expect the path to be closed for a fill. If you need to, because you want to also trace the outline, for colour bleed or some such, then you can used the close path command (z).
Enclosed areas
The good news is that this approach does not have to consider enclosed areas. We actually know if it is an enclosed area by the starting direction being 2 and not 0, but that does not actually matter. This tracing will always create a clockwise trace for an exterior path and a counter clockwise path for an interior path. The fill logic used by SVG means the inner path cancels our the outer path and creates exactly the effect you want.
Colours butting up
There is one possible issue when tracing multiple colours. The above will create the traces for each colour, but the areas of one colour will touch the areas of another. This should not be a problem in SVG or other contexts, but could be - i.e. depending on how things are rendered it could lead to an infinitesimally small gap between them - perhaps if the result is rotated or manipulated in some way.
To avoid this, we could change the trace logic to consider any colour of a higher number to be the same colour, and we know that the higher colour will be traced on top of this colour. If we do this we will have to clear the byte array of edges before each colour as we'll use the same edges.
Sadly this creates the same issue where we have the edge of two colours on top of each other, and any misalignment due to processing could leak one colour overlapping the other by an infinitesimally small amount.
So maybe not an issue worth bothering about.
Optimising the result
Another important point is not simply to use M and L for SVG. Doing so means absolute co-ordinates and a point for each end of each edge.
Instead, I simply made some functions that use M at the start and then relative co-ordinates using l, h, and v. The numbers are smaller, and using h (horizontal) and v (vertical) means only one value. In practice l is not used, but they are generic SVG path functions that could be used in other places.
The optimisation obviously has to consider that we have multiple points in a row and reduce to a simple line. In this case it was only necessary to consider multiple points either horizontally or vertically which reduce to a single h or v command.
The other optimisation is to use the point on the left of the edge you are facing when doing an exterior path, but the point on the right when doing an interior path. This means you always start and end on a corner, making the optimisation slightly easier.
Obviously if you want an SVG where the QR code pixels are bigger, as is often the case, then simply enclosing the entire thing in a g (group) with a scale is simplest and keeps the numbers in the paths smaller.
2017-10-16
Blip
I'd thought I'd share one of the challenges of my day today - a very minor thing but it shows why some software can be such a nightmare. Maybe I can explain it in a way that is easy enough for non engineers to understand.
Sometimes a computer may be doing something wrong. That happens. One example which customers will have noticed is our "blip graph".
What is wrong is pretty obvious in that it is meant to have red (logouts) and green (login) bits, and until a few minutes ago it was only green. It is not a big deal, or highest priority, which is why I am looking today and not yesterday. We use it mostly to identify issues with the network, so it is useful and did need fixing.
What did you change?
One of the key steps in diagnosis of something like this is to look at what you changed. You then try and see if there is some link between what you changed and what is going wrong. In many cases you can just look at the changes and the error sticks out like a sore thumb.
A perfect example would be if I had, for some reason, been working on the code that creates the blip graph from the database, or if I had been working on the code that puts the blip counts in to the database.
I would be able to look at my change, and wonder why my own testing had not shown the problem as well. There are tools to show me exactly what I changed.
It is also really useful if a problem is reported quickly as you also remember why you changed something and what you were trying to actually do as well.
We changed everything and nothing!
The problem is that we changed everything because we have done a major upgrade on clueless. We have also changed nothing, in that none of the code has been changed, just built on the new machine.
The code that makes the blip graph has not changed, and the code that displays the blip graph has not changed. Clearly the database is working as we have some of the blip graph. Indeed, it really made no sense.
Error logs?
One of the key things that lots of systems have are error logs, and we check these. But there are no errors being reported by the system that generates or displays the blip graphs after the upgrade, and were not in the past. So no clues there...
How did it ever work?
After a lot of digging I have found the cause, and it leads to one of those special things that can so often happen with software. HOW THE F*CK DID THIS EVER WORK?!
The "digging" took quite a few hours, because there simply was no logic to it. Nothing had been changed recently in the code, and no errors showing.
I quickly worked out that the displaying side was probably OK, but the database has zeros for the "logouts". The code to record the data looked the same for both login and logout, so how could it only be recording one side?
The eventual bug was a stupid mistake on my part in the code, written 8 years ago. I was comparing a data and time value with a time field in one case because of a simple typo. For the login side I did not have the same typo. It was subtle.
The problem is that the database server used to (silently) decide that I meant to just compare the time part, and get one with it and "just worked". Now, some change in the date/time logic in the database means that it considers the comparison not to match - though not an error, so it (silently) does nothing, instead.
The fix was therefore very simple, and now we have working blip graphs. Just one of dozens of small things to check today. So, if you do see thinking no quite right on clueless, do let us know.
I hope that gives some insight in to the perils of programming.
Sometimes a computer may be doing something wrong. That happens. One example which customers will have noticed is our "blip graph".
What did you change?
One of the key steps in diagnosis of something like this is to look at what you changed. You then try and see if there is some link between what you changed and what is going wrong. In many cases you can just look at the changes and the error sticks out like a sore thumb.
A perfect example would be if I had, for some reason, been working on the code that creates the blip graph from the database, or if I had been working on the code that puts the blip counts in to the database.
I would be able to look at my change, and wonder why my own testing had not shown the problem as well. There are tools to show me exactly what I changed.
It is also really useful if a problem is reported quickly as you also remember why you changed something and what you were trying to actually do as well.
We changed everything and nothing!
The problem is that we changed everything because we have done a major upgrade on clueless. We have also changed nothing, in that none of the code has been changed, just built on the new machine.
The code that makes the blip graph has not changed, and the code that displays the blip graph has not changed. Clearly the database is working as we have some of the blip graph. Indeed, it really made no sense.
Error logs?
One of the key things that lots of systems have are error logs, and we check these. But there are no errors being reported by the system that generates or displays the blip graphs after the upgrade, and were not in the past. So no clues there...
How did it ever work?
After a lot of digging I have found the cause, and it leads to one of those special things that can so often happen with software. HOW THE F*CK DID THIS EVER WORK?!
The "digging" took quite a few hours, because there simply was no logic to it. Nothing had been changed recently in the code, and no errors showing.
I quickly worked out that the displaying side was probably OK, but the database has zeros for the "logouts". The code to record the data looked the same for both login and logout, so how could it only be recording one side?
The eventual bug was a stupid mistake on my part in the code, written 8 years ago. I was comparing a data and time value with a time field in one case because of a simple typo. For the login side I did not have the same typo. It was subtle.
The problem is that the database server used to (silently) decide that I meant to just compare the time part, and get one with it and "just worked". Now, some change in the date/time logic in the database means that it considers the comparison not to match - though not an error, so it (silently) does nothing, instead.
The fix was therefore very simple, and now we have working blip graphs. Just one of dozens of small things to check today. So, if you do see thinking no quite right on clueless, do let us know.
I hope that gives some insight in to the perils of programming.
Subscribe to:
Posts (Atom)
-
Broadband services are a wonderful innovation of our time, using multiple frequency bands (hence the name) to carry signals over wires (us... -
For many years I used a small stand-alone air-conditioning unit in my study (the box room in the house) and I even had a hole in the wall fo... -
This is an appeal for (sensible) comments. I am working on revised A&A tariffs for broadband. For those that are not sure how they wor...