morzel.net

.net, js, html, arduino, java... no rants or clickbaits.

Short but very usueful regex – lookbehind, lazy, group and backreference

Recently, I wanted to extract calls to external system from log files and do some LINQ to XML processing on obtained data. Here’s a sample log line (simplified, real log was way more complicated but it doesn’t matter for this post):

Call:<getName seqNo="56789"><id>123</id></getName> Result:<getName seqNo="56789">John Smith</getName>

I was interested in XML data of the call:

<getName seqNo="56789">
  <id>123</id>
</getName>

Quick tip: super-easy way to get such nicely formatted XML in .NET 3.5 or later is to invoke ToString method on XElement object:

var xml = System.Xml.Linq.XElement.Parse(someUglyXmlString);     
Console.WriteLine(xml.ToString());

When it comes to log, some things were certain: 

  • call’s XML will be logged after “Call:” text on the beginning of line
  • call’s root element name will contain only alphanumerical chars or underscore
  • there will be no line brakes in call’s data
  • call’s root element name may also appear in the “Result” section

Getting to the proper information was quite easy thanks to Regex class:

Regex regex = new Regex(@"(?<=^Call:)<(\w+).*?</\1>");
string call = regex.Match(logLine).Value;

This short regular expressions has a couple of interesting parts. It may not be perfect but proved really helpful in log analysis. If this regex is not entirely clear to you - read on, you will need to use something similar sooner or later. 

Here’s the same regex with comments (RegexOptions.IgnorePatternWhitespace is required to process expression commented this way):

string pattern = @"(?<=^Call:) # Positive lookbehind for call marker
                   <(\w+)      # Capturing group for opening tag name
                   .*?         # Lazy wildcard (everything in between)
                   </\1>       # Backreference to opening tag name";   
Regex regex = new Regex(pattern, RegexOptions.IgnorePatternWhitespace);
string call = regex.Match(logLine).Value;

Positive lookbehind

(?<=Call:) is a lookaround or more precisely positive lookbehind. It’s a zero-width assertion that lets us check whether some text is preceded by another text. Here “Call:” is the preceding text we are looking for. (?<=something) denotes positive lookbehind. There is also negative lookbehind expressed by (?<!something).  With negative lookbehind we can match text that doesn’t have particular string before it. Lookaround checks fragment of the text but doesn't became part of the match value. So the result of this:

Regex.Match("X123", @"(?<=X)\d*").Value

Will be "123" rather than "X123".

.NET regex engine has lookaheads too. Check this awesome page if you want to learn more about lookarounds. 

Note: In some cases (like in our log examination example) instead of using positive lookaround we may use non-capturing group...

Capturing group

<(\w+) will match less-than sign followed by one or more characters from \w class (letters, digits or underscores). \w+ part is surrounded with parenthesis to create a group containing XML root name (getName for sample log line). We later use this group to find closing tag with the use of backreference. (\w+) is capturing group, which means that results of this group existence are added to Groups collection of Match object. If you want to put part of the expression into a group but you don’t want to push results into Groups collection you may use non-capturing group by adding a question mark and colon after opening parenthesis, like this: (?:something)

Lazy wildcard

.*? matches all characters except newline (because we are not using RegexOptions.Singleline) in lazy (or non-greedy) mode thanks to question mark after asterisk. By default * quantifier is greedy, which means that regex engine will try to match as much text as possible. In our case, default mode will result in too long text being matched:

<getName seqNo="56789"><id>123</id></getName> Result:<getName seqNo="56789">John Smith</getName>

Backreference

</\1> matches XML close tag where element's name is provided with \1 backreference. Remember the (\w+) group? This group has number 1 and by using \1 syntax we are referencing the text matched by this group. So for our sample log, </\1> gives us </getName>. If regex is complex it may be a good idea to ditch numbered references and use named references instead. You can name a group by <name> or ‘name’ syntax and reference it by using k<name> or k’name’. So your expression could look like this:

@"(?<=^Call:)<(?<tag>\w+).*?</\k<tag>>"

or like this:

@"(?<=^Call:)<(?'tag'\w+).*?</\k'tag'>"

The latter version is better for our purpose. Using < > signs while matching XML is confusing. In this case regex engine will do just fine with < > version but keep in mind that source code is written for humans…

Regular expressions look intimidating, but do yourself a favor and spend few hours practicing them, they are extremely useful (not only for quick log analysis)!

Fast pixel operations in .NET (with and without unsafe)

Bitmap class has GetPixel and SetPixel methods that let you acquire and change color of chosen pixels. Those methods are very easy to use but are also extremely slow. My previous post gives detailed explanation on the topic, click here if you are interested.

Fortunately you don’t have to use external libraries (or resign from .NET altogether) to do fast image manipulation. The Framework contains class called ColorMatrix that lets you apply many changes to images in an efficient manner. Properties such as contrast or saturation can be modified this way. But what about manipulation of individual pixels? It can be done too, with the help from Bitmap.LockBits method and BitmapData class…

Good way to test individual pixel manipulation speed is color difference detection. The task is to find portions of an image that have color similar to some chosen color. How to check if colors are similar? Think about color as a point in three dimensional space, where axes are: red, green and blue. Two colors are two points. The difference between colors is described by the distance between two points in RGB space.

Colors as points in 3D space diff = sqrt((C1R-C2R)2+(C1G-C2G)2+(C1B-C2B)2)

This technique is very easy to implement and gives decent results. Color comparison is actually a pretty complex matter though. Different color spaces are better suited for the task than RGB and human color perception should be taken into account (e. g. our eyes are more keen to detect difference in shades of green that in shades of blue). But let’s keep things simple here…

Our test image will be this Ultra HD 8K (7680x4320, 33.1Mpx) picture* (on this blog it’s of course scaled down to save bandwidth):

Color difference detection input image (scaled down for blog)

This is a method that may be used to look for R=253 G=129 B=84 pixels (aka “pink bra”). It sets matching pixels as white (the rest will be black):

static void DetectColorWithGetSetPixel(Bitmap image, byte searchedR, byte searchedG, int searchedB, int tolerance)
{
    int toleranceSquared = tolerance * tolerance;
    
    for (int x = 0; x < image.Width; x++)
    {
        for (int y = 0; y < image.Height; y++)
        {
            Color pixel = image.GetPixel(x, y);

            int diffR = pixel.R - searchedR;
            int diffG = pixel.G - searchedG;
            int diffB = pixel.B - searchedB;

            int distance = diffR * diffR + diffG * diffG + diffB * diffB;

            image.SetPixel(x, y, distance > toleranceSquared ? Color.Black : Color.White);
        }
    }
}

Above code is our terribly slow Get/SetPixel baseline. If we call it this way (named parameters for clarity):

DetectColorWithGetSetPixel(image, searchedR: 253, searchedG: 129, searchedB: 255, tolerance: 84);

we will receive following outcome:

Color difference detection output image (scaled down)

Result may be ok but having to wait over 84300ms* is a complete disaster! 

Now check out this method:

static unsafe void DetectColorWithUnsafe(Bitmap image, byte searchedR, byte searchedG, int searchedB, int tolerance)
{
    BitmapData imageData = image.LockBits(new Rectangle(0, 0, image.Width, image.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
    int bytesPerPixel = 3;

    byte* scan0 = (byte*)imageData.Scan0.ToPointer();
    int stride = imageData.Stride;

    byte unmatchingValue = 0;
    byte matchingValue = 255;
    int toleranceSquared = tolerance * tolerance;

    for (int y = 0; y < imageData.Height; y++)
    {
        byte* row = scan0 + (y * stride);

        for (int x = 0; x < imageData.Width; x++)
        {
            // Watch out for actual order (BGR)!
            int bIndex = x * bytesPerPixel;
            int gIndex = bIndex + 1;
            int rIndex = bIndex + 2;

            byte pixelR = row[rIndex];
            byte pixelG = row[gIndex];
            byte pixelB = row[bIndex];

            int diffR = pixelR - searchedR;
            int diffG = pixelG - searchedG;
            int diffB = pixelB - searchedB;

            int distance = diffR * diffR + diffG * diffG + diffB * diffB;

            row[rIndex] = row[bIndex] = row[gIndex] = distance > toleranceSquared ? unmatchingValue : matchingValue;
        }
    }

    image.UnlockBits(imageData);
}

It does exactly the same thing but runs for only 230ms over 360 times faster!

Above code makes use of Bitmap.LockBits method that is a wrapper for native GdipBitmapLockBits (GDI+, gdiplus.dll) function. LockBits creates a temporary buffer that contains pixel information in desired format (in our case RGB, 8 bits per color component). Any changes to this buffer are copied back to the bitmap upon UnlockBits call (therefore you should always use LockBits and UnlockBits as a pair). Bitmap.LockBits returns BitmapData object (System.Drawing.Imaging namespace) that has two interesting properties: Scan0 and Stride. Scan0 returns an address of the first pixel data. Stride is the width of single row of pixels (scan line) in bytes (with optional padding to make it dividable by 4). 

BitmapData layout

Please notice that I don’t use calls to Math.Pow and Math.Sqrt to calculate distance between colors. Writing code like this: 

double distance = Math.Sqrt(Math.Pow(pixelR - searchedR, 2) + Math.Pow(pixelG - searchedG, 2) + Math.Pow(pixelB - searchedB, 2));

to process millions of pixels is a terrible idea. Such line can make our optimized method about 25 times slower! Using Math.Pow with integer parameters is extremely wasteful and we don’t have to calculate square root to determine if distance is longer than specified tolerance.

Previously presented method uses code marked with unsafe keyword. It allows C# program to take advantage of pointer arithmetic. Unfortunately, unsafe mode has some important restrictions. Code must be compiled with \unsafe option and executed for fully trusted assembly. 

Luckily there is a Marshal.Copy method (from System.Runtime.InteropServices namespace) that can move data between managed and unmanaged memory. We can use it to copy image data into a byte array and manipulate pixels very efficiently. Look at this method:

static void DetectColorWithMarshal(Bitmap image, byte searchedR, byte searchedG, int searchedB, int tolerance)
{        
    BitmapData imageData = image.LockBits(new Rectangle(0, 0, image.Width, image.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);

    byte[] imageBytes = new byte[Math.Abs(imageData.Stride) * image.Height];
    IntPtr scan0 = imageData.Scan0;

    Marshal.Copy(scan0, imageBytes, 0, imageBytes.Length);
  
    byte unmatchingValue = 0;
    byte matchingValue = 255;
    int toleranceSquared = tolerance * tolerance;

    for (int i = 0; i < imageBytes.Length; i += 3)
    {
        byte pixelB = imageBytes[i];
        byte pixelR = imageBytes[i + 2];
        byte pixelG = imageBytes[i + 1];

        int diffR = pixelR - searchedR;
        int diffG = pixelG - searchedG;
        int diffB = pixelB - searchedB;

        int distance = diffR * diffR + diffG * diffG + diffB * diffB;

        imageBytes[i] = imageBytes[i + 1] = imageBytes[i + 2] = distance > toleranceSquared ? unmatchingValue : matchingValue;
    }

    Marshal.Copy(imageBytes, 0, scan0, imageBytes.Length);

    image.UnlockBits(imageData);
}

It runs for 280ms, so it is only slightly slower than unsafe version. It is CPU efficient but uses more memory then previous method – almost 100 megabytes for our test Ultra HD 8K image in RGB 24 format.

If you want to make pixel manipulation even faster you may process different parts of the image in parallel. You need to make some benchmarking first because for small images the cost of threading may be bigger than gains from concurrent execution. Here’s a quick sample of code that uses 4 threads to process 4 parts of the image simultaneously. It yields 30% time improvement on my machine. Treat is as a quick and dirty hint, this post is already to long…

static unsafe void DetectColorWithUnsafeParallel(Bitmap image, byte searchedR, byte searchedG, int searchedB, int tolerance)
{
    BitmapData imageData = image.LockBits(new Rectangle(0, 0, image.Width, image.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
    int bytesPerPixel = 3;

    byte* scan0 = (byte*)imageData.Scan0.ToPointer();
    int stride = imageData.Stride;

    byte unmatchingValue = 0;
    byte matchingValue = 255;
    int toleranceSquared = tolerance * tolerance;

    Task[] tasks = new Task[4];
    for (int i = 0; i < tasks.Length; i++)
    {
        int ii = i;
        tasks[i] = Task.Factory.StartNew(() =>
            {
                int minY = ii < 2 ? 0 : imageData.Height / 2;
                int maxY = ii < 2 ? imageData.Height / 2 : imageData.Height;

                int minX = ii % 2 == 0 ? 0 : imageData.Width / 2;
                int maxX = ii % 2 == 0 ? imageData.Width / 2 : imageData.Width;                        
                
                for (int y = minY; y < maxY; y++)
                {
                    byte* row = scan0 + (y * stride);

                    for (int x = minX; x < maxX; x++)
                    {
                        int bIndex = x * bytesPerPixel;
                        int gIndex = bIndex + 1;
                        int rIndex = bIndex + 2;

                        byte pixelR = row[rIndex];
                        byte pixelG = row[gIndex];
                        byte pixelB = row[bIndex];

                        int diffR = pixelR - searchedR;
                        int diffG = pixelG - searchedG;
                        int diffB = pixelB - searchedB;

                        int distance = diffR * diffR + diffG * diffG + diffB * diffB;

                        row[rIndex] = row[bIndex] = row[gIndex] = distance > toleranceSquared ? unmatchingValue : matchingValue;
                    }
                }
            });
    }

    Task.WaitAll(tasks);

    image.UnlockBits(imageData);
}

* Originally I had some triangles and squares as an illustration, but Victoria's Secret models (source) are better, huh? :) 

* .NET 4 console app, executed  on MSI GE620 DX laptop: Intel Core i5-2430M 2.40GHz (2 cores, 4 threads), 4GB DDR3 RAM, NVIDIA GT 555M 2GB DDR3, HDD 500GB 7200RPM, Windows 7 Home Premium x64.

Ref modifier for reference types and a bit of SOS

Take a look at the following code and think what value will be displayed on the console (note that string is a reference type)?

using System;
               
class Program
{
    static void Test(string y)
    {
        y = "bbb";
    }

    static void Main()
    {
        string x = "aaa";
        Test(x);
        Console.WriteLine(x);
    }
}

The correct answer (aaa) is not all that obvious. You will see the words aaa, because without a ref modifier, a program written in C# provides a copy of the parameter value (for value types) or a copy of a reference (for reference types).

When parameter y in method Test receives a new text value, CLR does not modify the array of chars. Instead, a new string is created and a reference to it is assigned to variable y (more info here). Variable y contained in method Test is, however, just a copy of a reference hold under x variable from method named Main.

To actually change the text hidden under x variable, use the ref modifier (you have to set it both in the method declaration and its invocation - C# enforces such behavior for clarity):

using System;
               
class Program
{
    static void Test(ref string y)
    {
        y = "bbb";
    }

    static void Main()
    {
        string x = "aaa";
        Test(ref x);
        Console.WriteLine(x);
    }
}

After this change, console will show bbb text.

 

SOS

Way in which parameters are passed to a method can be examined by using tool called SOS (Son of Strike). We will use CLRStack -a command, which displays information about parameters and local variables on managed code stack (if you don't know how to use SOS look here and here, if you wonder where the name "Son of Strike" came from, click here)...

Below are the results of CLRStack -a command executed at the time of entry to the Test method.

For code without ref modifier:

!CLRStack -a
OS Thread Id: 0x176c (5996)
Child SP IP       Call Site
0031f114 00390104 Program.Test(System.String)
    PARAMETERS:
        y (0x0031f114) = 0x025cb948

0031f158 003900af Program.Main()
    LOCALS:
        0x0031f158 = 0x025cb948

0031f3c0 656721bb [GCFrame: 0031f3c0]

For code with ref modifier:

!CLRStack -a
OS Thread Id: 0x934 (2356)
Child SP IP       Call Site
001dee34 002f00f4 Program.Test(System.String ByRef)
    PARAMETERS:
        y (0x001dee34) = 0x001dee78

001dee78 002f00aa Program.Main()
    LOCALS:
        0x001dee78 = 0x027fb948

001df0ec 656721bb [GCFrame: 001df0ec]

An important difference that is exhibited by these results is the value of y parameter. In the case of code without ref modifier, it is the address of aaa string (0x025cb948). For the code with ref modifier, the value of y parameter is the address of x variable (0x001dee78) from Main method (that variable points to aaa string).

BadImageFormatException, x86 i x64

Have you ever seen BadImageFormatException or “An attempt was made to load a program with an incorrect format” message?

If so, maybe the program that you tried to run hasn’t been compiled with /platform:x86 option. You are probably wondering why, while writing in C# you should think about what kind of machine (x86 or x64) your program will execute on. Well… in most cases you don’t have to care about it. If your application doesn’t contain any unsafe code and doesn’t import any native modules that are destined for specific CPU architecture, then you can forget about 32/64 bit dilemma. After all C# code gets compiled into intermediate language (CIL) and upon execution framework’s just-in-time compiler will emit native instructions suitable for current platform. Great, but there’s a catch…

Imagine a situation when you import 32 bit DLL in your application. If you run that software on 32 bit operating system everything works as expected. Unfortunately on x64 machine you can get BadImageFormatException while trying to load DLL. Why? Your assembly may be compiled with /platform:anycpu setting. It means that on 32 bit systems your code will be executed with 32 bit CLR version. On 64 bit systems a 64 bit process will be used – and it will cause problems with loading 32 bit DLL. If you provide /platform:x86 setting, then 32 bit version of the CLR will be choosen even on the x64 versions of Windows (utilizing WoW64: Windows 32-bit on Windows 64-bit).

In Visual Studio 2010 you can set targeted platform in project “Properties” window (on “Build” tab). To get there, right click on project file in Solution Explorer and choose “Properties” or use main menu “Project | <you project name> Properties…”.

Setting targeted platform in Visual Studio (click to enlarge)

Microsoft has created useful tool called CorFlags which can be used to show or set the targeted platform of an managed assembly. You can access this program by using Visual Studio Command Prompt or find it directly on your disk (I have it under C:\Program Files\Microsoft.NET\SDK\v2.0\Bin\CorFlags.exe).

Here are some examples of what you may see after checking an EXE file created with various /platform option values (use CorFlags file.name command to check a file):

anycpu x86 x64
Version   : v4.0.30319
CLR Header: 2.5
PE        : PE32
CorFlags  : 1
ILONLY    : 1
32BIT     : 0
Signed    : 0
Version   : v4.0.30319
CLR Header: 2.5
PE        : PE32
CorFlags  : 3
ILONLY    : 1
32BIT     : 1
Signed    : 0
Version   : v4.0.30319
CLR Header: 2.5
PE        : PE32+
CorFlags  : 1
ILONLY    : 1
32BIT     : 0
Signed    : 0

For the scope of this post 2 rows of the CorFlags output are important: PE and 32BIT.

  • PE: PE32 means that file can be executed on both x86 and x64
  • PE: PE32+ means that it can only be run on 64 bit version of OS
  • 32BIT: 1 means that program must be executed on x86 environment.

Understanding 32BIT: 1 meaning is really important if you want to avoid problems with importing 32 bit DLL on 64 bit systems. If 32BIT flag is set and you run PE32 file on x64, then your app will be executed in 32 bit process (under WoW), hence will have a chance to properly import 32 bit DLL. Without this setting 64 bit environment will be chosen which will cause problems.

The good news is that you can easily modify 32BIT flag with CorFlags tool, to do this execute that command:

CorFlags file.exe /32BIT+

And to remove it, try this

CorFlags file.exe /32BIT-

So even if you cannot recompile problematic assembly with proper /platform option you still have a chance of using legacy 32 bit DLLs on 64 bit Windows :)

Why the use of GetPixel and SetPixel is so inefficient!

Bitmap class provides two simple methods: GetPixel and SetPixel used respectively to retrieve a point of image (as the Color structure) and set a point of image. The following code illustrates how to retrieve/set all the pixels in the bitmap:

private void GetSetPixel(Bitmap image) {
   for (int x = 0; x < image.Width; x++) {
      for (int y = 0; y < image.Height; y++) {
         Color pixel = image.GetPixel(x, y);
         image.SetPixel(x, y, Color.Black);
      }
   } 
}

As shown, review and modification of pixels is extremely simple. Unfortunately behind the simplicity of the code lies a serious performance trap. While for a small number of references to image points, the speed at which GetPixel and SetPixel work is good enough, for larger images it is not the case. Graph presented below can serve as a proof of that. It shows results of 10 tests* which consisted of 10-fold invocation of previously shown GetSetPixel method for images 100x100 and 1000x1000 pixels in size.

Wyniki testów prędkości operacji na pikselach obrazu z użyciem metod GetPixel i SetPixel klasy Bitmap.

The average test time for an image measuring 100 by 100 pixels was 543 milliseconds. This speed is acceptable if the image processing is not done frequently. Performance problem is, however, clearly visible when you try to use an image of size 1000 per 1000 pixels. Execution of the test in this case takes an average of more than 41 seconds - more than 4 sec. on a single call to GetSetPixel (seriously!).

Why so slow?

Low efficiency is due to the fact that access to the pixel is not a simple reference to a memory area. Each getting or setting of color is associated with invocation of .NET Framework method, which is a wrapper for native function contained in gdiplus.dll. This call is through the mechanism of P/Invoke (Platform Invocation), which is used to communicate from managed code to unmanaged API (API outside of the .NET Framework). So for a bitmap of 1000x1000 pixels there will be 1 million calls to GetPixel method that besides the validation of parameters uses the native GdipBitmapGetPixel function. Before returning color information, GDI+ function has to perform such operations as calculating the position of bytes responsible for description of desired pixel… Similar situation occurs in the case SetPixel method.

Look at the following code of Bitmap.GetPixel method obtained with the .NET Reflector (System.Drawing.dll, .NET Framework 2.0):

public Color GetPixel(int x, int y) {
   int argb = 0;
   if ((x < 0) || (x >= base.Width)) {
      throw new ArgumentOutOfRangeException(“x”, SR.GetString(“ValidRangeX”));
   }
   if ((y < 0) || (y >= base.Height)) {
      throw new ArgumentOutOfRangeException(“y”, SR.GetString(“ValidRangeY”));
   }
   
   int status = SafeNativeMethods.Gdip.GdipBitmapGetPixel(new HandleRef(this, base.nativeImage), x, y, out argb);
   if (status != 0) {
      throw SafeNativeMethods.Gdip.StatusException(status);
   }
   return Color.FromArgb(argb);
}

Here is import of GDI + function:

[DllImport(“gdiplus.dll”, CharSet=CharSet.Unicode, SetLastError=true, 
ExactSpelling=true)]
internal static extern int GdipBitmapGetPixel(HandleRef bitmap, int x, int y, out int argb);

* I have tested on such laptop: HP Pavilion dv5, AMD Turion X2 Dual-Core Mobile RM-70, 3 GB RAM, Vista Home Premium