Showing posts with label c#. Show all posts
Showing posts with label c#. Show all posts

Monday, December 26, 2011

Philips Healthcare's Sierra ECG format XLI Compression Scheme

One of the services I work for has recently acquired a Philips HeartStart MRx cardiac monitor. It came complete with Bluetooth transmission of 12-Lead and event data. At roughly the same time our service installed a computer, an MDT, into the cab of our unit to interface with our county's CAD software.

Naturally I linked our monitor and our MDT via Bluetooth, and transmitted a 12-Lead from a rhythm generator. When the file landed on the MDT, I looked for an application to view the 12-Leads and rhythm strips, however, none appeared to be able to use the file as-is.

For the non-technical, the ECGs are shipped compressed--somewhat like a ZIP file--which contains all of your monitored vital signs, printed rhythm strips, and your 12-Leads. The format of the 12-Leads is an Open Standard; Philips Healthcare provides most of the details needed to use the files. The 12-Lead data is also compressed to save space. Unfortunately, there is no documentation which tells you how to decompress the 12-Lead data.

The technically-faint-of-heart should skip these next bits.

For the technical, the ECGs are contained in a Gzip'd TAR archive. The 12-Leads are stored inside in an XML format known as the Sierra ECG format (currently at version 1.03 or 1.04, as far as I can tell). Inside this XML format is Base64 encoded, XLI compressed data comprising the acquired leads during a 12-Lead (up to 16 leads appear to be able to be stored).

I searched for a description of the XLI compression format, however, I was only able to find a reference implementation for Microsoft Windows which simply decoded the files. No code or description was provided, and the implementation itself is not portable. (ed: it appears this may be a reference to the HP PageWriter XLi which Philips acquired)

At this point I decided my only option was to reverse engineer the XLI Compression format, and began with simple guesses. I tried decompressing the data using Deflate, Zip, and RLE without any progress. I was able to determine that the first 8 bytes of the compressed data included a compressed length, some uncompressed data, and that each of the 12 to 16 leads were stored in a chunk with one of these headers:
offset   2        4        6        8  ...
+--------+--------+--------+--------+--------+--------+--------+
| Size            |  Unk.  | Delta? | Compressed data...       |
+--------+--------+--------+--------+                          |
| ...                                             [Size bytes] |
+--------+--------+--------+--------+--------+--------+--------+
| Next lead chunk ...                                          |
Once the simple guesses were ruled out, I began exploring the behavior of the reference implementation provided for the Sierra ECG format. Using OllyDbg I noticed certain code tells which made me believe the decompression algorithm read 10-bits at a time:
SHR   EAX, 16h   ; reduce EAX to the 10-bit code word
SHL   ECX, Ah    ; prepare to read 10 more bits from the input
The compressed data also did not appear to contain a compression dictionary referenced by the code. At this point I considered I was looking at a form of Lempel-Ziv-Welch, or LZW, compression. LZW is a popular, lossless compression scheme which creates its compression dictionary on the fly. It is used by the GIF and TIFF image formats, and was the subject of controversy when it was first introduced into the GIF format due to patent licensing requirements.

In my quest to quickly reach a conclusion I found an excellent LZW implementation from Mark Nelson in C and it successfully decompressed the data. In fact, the structure of the C code was so familiar, I realized the reference implementation from Philips used the exact same code!

If you've reached this step while following along at home, you'll notice the decompressed data seems front-loaded with 0's. This is a case of intelligently streaming the data to the compression algorithm to take advantage of data duplication.

The uncompressed data represents 16-bit delta codes, of which the majority include 0x00 or 0xFF in their most significant byte (MSB). This is because they are either small and positive or small and negative, and as ECG data is rhythmic the delta codes are likely to retain the same sign for numerous samples.

To take advantage of this fact during compression, the delta codes are first deinterleaved into two halves. The first half includes each MSB and the second half includes each LSB. The pseudo-code for interleaving the decompressed data looks like the following:
# input contains the decompressed data
# output will contain the interleaved 16-bit delta codes
fun unpack( input[], output[], nSamples )
    for i <- 1..nSamples
        output[i] <- (input[i] << 8) | input[nSamples + i]
    endfor
endfun
At this point the delta compression scheme will need to be decoded to produce the actual signal data for each of the leads. The delta compression scheme is a simple recurrence relation (a second order difference relation) using the prior two delta codes:
# output contains the 16-bit delta codes
# first is the 16-bit delta code from the chunk header
fun deltaDecompression( output[], nSamples, first )
    x <- output[1]
    y <- output[2]
    prev <- first
    for i <- 3..nSamples
        z <- (2 * y) - x - prev
        prev <- output[i] - 64   # is -64 to 64 the range?
        output[i] <- z
        x <- y
        y <- z
    endfor
endfun
Now that you have the actual, per signal data all you need to do is recreate leads III, aVR, aVL, and aVF. This is done using the data from leads I and II as on most ECG machines. I've omitted the actual formulas for brevity.

Using my reference implementation of the decompression algorithm I was able to feed the original acquired 12-Lead to the Philips ECG to SVG converter, with the following results:


If you'd like to start playing with my code I welcome you to join my Github Project: sierra-ecg-tools. I am also working on a C implementation, and likely an Android implementation. Stay tuned, and apologies for the technical post.

The author has no financial ties to Philips Healthcare and received no compensation for this work.

Friday, December 11, 2009

Code Review Find

double PIE = 3.141592654;
No, that code did not pass the review.

Monday, July 13, 2009

Replacing Invalid Characters v. Performance

It appears a large amount of StackOverflow posts focus on eeking out an impossible amount of performance for rather mundane tasks. Sometimes, when you read the question, you can't help but wonder why they even want to improve the performance of the given algorithm. The odds are most performance enhancements would come at the expense of readability. However, that does not mean it isn't worth taking a look at--especially if you're bored and don't want to do something else.

I had some fun with the following question: Most efficient way to remove special characters from string. Just from looking at the specification given, my guess is this is going to get called maybe 100 times at the most. O(f(n)) where n is 100 is boring. Even more interesting is that the given solution from the poster is already quite good (barring a logic error). Here is the OP's solution without any logical errors:

public static string RemoveSpecialCharacters(string str)
{
StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.Length; ++i)
{
if ((str[i] >= '0' && str[i] <= '9')
|| (str[i] >= 'A' && str[i] <= 'Z')
|| (str[i] >= 'a' && str[i] <= 'z')
|| (str[i] == '.' || str[i] == '_'))
sb.Append(str[i]);
}
return sb.ToString();
}

As a frequent code reviewer, I think this method looks great. In fact, running this method against a corpus of 10000 randomly generated lines with 4096 characters executes in 0.0479ms/string. This is very fast. The simplest improvement would be to prefill the StringBuilder to str.Length characters. This results in a new runtime of 0.0442ms/string. Now we're cooking with gas!

A few posters suggested regular expressions. Well, the naive approach (uncompiled) takes 0.489ms/string which is 10 times slower. Making the regular expression compiled takes 0.363ms/string, still 8 times slower. However, take a look at the new code you must maintain:

static Regex replacer = new Regex(@"[^a-zA-Z0-9_.]+", RegexOptions.Compiled);
public static string RemoveSpecialCharacters(string str)
{
return replacer.Replace(str, String.Empty);
}

Ok, so a big drop in performance, but perhaps a big gain in readability and maintainability. However, the OP's algorithm is surely very simple to read. So the regular expressions make sense if this method is going to be called a few times on small strings.

Another suggestion was to use foreach rather than a for-loop. This results in another minor speedup to 0.0412ms/string. The last of the improvements suggested was to go with a lookup table. Personally it is my least favorite because it will be less readable and maintainable. C# 3.0 can help us some, using LINQ to improve those.

static bool[] allowedChars = new List<bool>(
from ii in Enumerable.Range(0, 128)
let c = (char)ii
select (c >= '0' && c <= '9')
|| (c >= 'A' && c <= 'Z')
|| (c >= 'a' && c <= 'z')
|| (c == '.')
|| (c == '_')
).ToArray();

public static string RemoveSpecialCharacters(string str)
{
StringBuilder sb = new StringBuilder(str.Length);
for (int ii = 0; ii < str.Length; ++ii)
{
if (str[ii] < allowedChars.Length && allowedChars[str[ii]])
sb.Append(str[ii]);
}
return sb.ToString();
}

Take a look at how many extra lines of code we have added. This solution may be the fastest so far, at 0.0399ms/string, but it is also bordering on the ugliest. However, we haven't even touched on the simplest improvement that can be made which results in the largest absolute increase in performance. If you replace the StringBuilder with a char[] a 100% speedup can be achieved!

public static string RemoveSpecialCharacters(string str)
{
int idx = 0;
char[] chars = new char[str.Length];
foreach (char c in str)
{
if ((c >= '0' && c <= '9')
|| (c >= 'A' && c <= 'Z')
|| (c >= 'a' && c <= 'z')
|| (c == '.') || (c == '_'))
{
chars[idx++] = c;
}
}
return new string(chars, 0, idx);
}

This method runs in a blazing 0.0299ms/string, is simple to read, is easy to maintain, and is highly performant. We have a winner folks.

Tuesday, March 3, 2009

Exceptions and Constructors

You should never include any work in a constructor which may leave the object in an inconsistant state. Constructors should be atomic and consistant. You should avoid having side effects in a constructor. However, sometimes you cannot avoid doing additional work in a constructor.

For example, you are designing a stream like class which acquires an unmanaged resource in the constructor. Following RAII, you implement the necessary logic to clean up your unmanaged resource in Dispose and Finalize. Given the following pseudo-code, what is a possible error condition we are not current designed to handle:
public MyType()
{
Check.Invariant(argumentInvariant1);
// ...
Check.Invariant(argumentInvariantN);

// 1. ACQUIRE
this.AcquireUnmanagedResource();

// 2. Set up our base properties from the resource
this.RetrieveConfiguration();
}

~MyType()
{
this.Dispose(false);
}

public void Dispose()
{
this.Dispose(true);
GC.SupressFinalize(this);
}

private void Dispose(bool disposing)
{
if (!this.isDisposed)
{
// RELEASE
this.ReleaseUnmanagedResource();

if (disposing)
{
this.DisposeManagedResources();
}
}
}
What would happen if #2 threw an exception? Well, it is more obvious in this example than in most code in the wild, but our Dispose or Finalize will not be called! Our unmanaged resource will not be released, and we will be leaked.

An appropriate solution would, perhaps, be the following modification to the constructor:
public MyType()
{
Check.Invariant(argumentInvariant1);
// ...
Check.Invariant(argumentInvariantN);

try
{
// 1. ACQUIRE
this.AcquireUnmanagedResource();

// 2. Set up our base properties from the resource
this.RetrieveConfiguration();
}
catch(Exception)
{
// RELEASE
this.Dispose(true);

throw; // propagate the exception
}
}
Now, if #2 should fail we will release the unmanaged resource and not leak anything. Keep in mind this will require a Dispose method which is resistant to an inconsistant object state. However, the design contract for IDisposable basically requires this anyways.

Monday, February 16, 2009

C# XML Documentation Guide

Today I found what is perhaps the most comprehensive guide to writing good C# XML Documentation. Many thanks to the Dynicity guys for producing this.

Monday, May 12, 2008

WPF Application Quality Guide v0.2

Microsoft has released v0.2 of their WPF Application Quality Guide, which contains some great new items in the application testing section. They go over some interesting ways you can test a GUI application, including media sections of an application. I must say I hadn't thought about taking a screenshot of the desired result and then using an image differencing tool on the user's screenshot as a method of acceptance testing. That section definitely got me thinking on how to streamline our own GUI testing practices (read: nonexistent). I have cleaned up versions of their sample code, and if you'd like it just shoot me an email.

Friday, March 7, 2008

WPF TileBrush Nonsense

For the absolute life of me I cannot get a custom TileBrush to tile outside of VS2k8 or Blend 2.5. The basics are that I'm constructing a ruler, which started programmatically after finding the current DPI. When that didn't work, I attempted to do the same thing in straight XAML, which wouldn't be relative to the DPI (thus would only be a nice ruler at 96dpi). Even this would not work. At this point my frustration knows no bounds.

The above is a screengrab from inside VS2k8. The screengrab from Blend 2.5 also shows the ruler tiling. Below is a screengrab during runtime, notice the distinctive lack of tiling, and now it is somehow stretching to Fill.

The tiled brush is a DrawingBrush consisting of a GeometryDrawing with a GeometryGroup of LineGeometry's. The annotated XAML is given below:
<DrawingBrush x:Key="RulerBrush"
Stretch="None"
TileMode="Tile"
Viewport="0,0,96,16"
ViewportUnits="Absolute"
Viewbox="0 0 1 1"
ViewboxUnits="RelativeToBoundingBox">
<DrawingBrush.Drawing>
<GeometryDrawing>
<GeometryDrawing.Geometry>
<GeometryGroup>
<LineGeometry EndPoint="0,16"
StartPoint="0,0" />
<!-- ... -->
<LineGeometry EndPoint="48,16"
StartPoint="48,4" />
<!-- ... -->
<LineGeometry EndPoint="96,16"
StartPoint="96,0" />
</GeometryGroup>
</GeometryDrawing.Geometry>
<GeometryDrawing.Pen>
<Pen Brush="#FF000000"
Thickness="1" />
</GeometryDrawing.Pen>
</GeometryDrawing>
</DrawingBrush.Drawing>
</DrawingBrush>

And the requisite XAML for the display area:
<Window xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
x:Class="Test.Window1"
x:Name="Window"
Title="Window"
Width="640"
Height="480">
<DockPanel x:Name="LayoutRoot" LastChildFill="True">
<ToolBarTray x:Name="ToolBarTray"
DockPanel.Dock="Top">
<ToolBar x:Name="MenuToolBar"
ToolBar.Band="0"
Width="{Binding Path=ActualWidth, ElementName=ToolBarTray}" />
</ToolBarTray>
<Rectangle x:Name="RulerY"
DockPanel.Dock="Left"
Height="15" Margin="0,15,0,0"
Fill="{DynamicResource RulerBrush}">
<Rectangle.LayoutTransform>
<RotateTransform Angle="-90.0" />
</Rectangle.LayoutTransform>
</Rectangle>
<Rectangle x:Name="RulerX"
DockPanel.Dock="Top"
Height="15" Margin="0,0,0,0"
Fill="{DynamicResource RulerBrush}"/>
<ScrollViewer Style="{DynamicResource SimpleScrollViewer}"/>
</DockPanel>
</Window>

This is fairly obnoxious!

Friday, February 8, 2008

Writing Quality WPF Applications

I've got together a few resources which are helpful when attempting to write a quality WPF application. While some of them are for C# 2.0 or .Net 2.0, I feel they are just as valid in C# 3.0 and .Net 3.5.

Without further ado, the (currently short) list:
Hopefully in the future there will be more guides for effective WPF development!

Thursday, January 24, 2008

Where the &%$@ is HashSet?

If you've created a .Net 3.5 project in Expression Blend 2 (December Preview) and then opened it up in VS2k8, you may have noticed that using System.Collections.Generic does not give you HashSet.
The type or namespace name 'HashSet' could not be found.
You may be gnashing your teeth over this, but the simple solution is to add System.Core.dll as a reference to your project because it appears Blend 2 leaves this out.

Update: Zoom multiple controls from the same slider in XAML

I've had a serious learning curve with XAML, and frequently find new and better ways of doing things. A good example of this is zooming multiple controls from the same slider. My previous solution used a DependencyProperty and an IValueConverter and was probably slow as dirt if you wired up more than a few controls to get zoomed. A much more succinct, maintainable, and readable solution would be:
<Page class="ZoomTest.Page1" name="page" xmlns="...">
xmlns:local="clr-namespace:ZoomTest"
local:AttachedProperties.Zoom="0.8">
<Grid>
<Grid.LayoutTransform>
<ScaleTransform ScaleX="{Binding Path=Zoom,
ElementName=page}"
ScaleY="{Binding Path=Zoom,
ElementName=page}" />
</Grid.LayoutTransform>
</Grid>
</Page>
And yes, while I do have two bindings, it actually is very fast. One of the big things I've learned is you can really (ab)use the binding system and strangely enough have a faster UI than one you control! In a GUI application I'm designing in WPF, there are over 5000 data bindings on just one page, and yet it is nearly twice as fast as the version where I practically precompute the whole UI! My only guess as to why this is the case is that UIElement's are much more expensive than data bindings.

Another way to tackle the above problem, if say you're on the same UI without Page's, is actually much simpler:
<Window ...>
<DockPanel x:Name="LayoutRoot"
LastChildFill="True">
<StackPanel DockPanel.Dock="Top">
<Slider x:Name="ZoomSlider"
Minimum="1" Value="5" Maximum="10" />
</StackPanel>
<ScrollViewer>
<Grid x:Name="content">
<Grid.LayoutTransform>
<ScaleTransform ScaleX="{Binding Path=Value,
ElementName=ZoomSlider}"
ScaleY="{Binding Path=Value,
ElementName=ZoomSlider}" />
</Grid.LayoutTransform>
</Grid>
</ScrollViewer>
</DockPanel>
</Window>
Using strategies like this you can use less C# and more XAML. I've been able to take over 7000 lines of presentation code written for Java 1.4 (the C# 2.0 code would be roughly the same size) and turn it into roughly 550 lines of XAML and 100 lines of C# 3.0. Expect more little fun things you can do with WPF soon (like making a ListBox do whatever you please).

Thursday, December 13, 2007

Zoom multiple controls from the same slider in XAML

Recently we've been playing around with XAML and WPF at work, and a common situation we run across is wanting to zoom different Page's without having separate zoom functionality. One slider should be enough to zoom any Page we hook up.

The basics start with an attached DependencyProperty called Zoom.
public static class AttachedProperties
{
public static readonly DependencyProperty ZoomProperty
= DependencyProperty.RegisterAttached("Zoom", typeof(double), typeof(UIElement),
new FrameworkPropertyMetadata(1.0,
FrameworkPropertyMetadataOptions.AffectsRender, null /* PropChangedCallback */,
new CoerceValueCallback((obj, value) => (double)value < 0.0 ? 0.0 : (double)value)));

public static double GetZoom(DependencyObject obj)
{
return (double)obj.GetValue(ZoomProperty);
}

public static void SetZoom(DependencyObject obj, object value)
{
double val = Double.Parse(value.ToString());
obj.SetValue(ZoomProperty, val);
}
}
Now we have an attached property we can connect to any UI Element! Notice that I suffixed 'Zoom' with '-Property' for the static variable, yet gave RegisterAttached just 'Zoom'. This is by convention (coincidentally so are the Get/Set pair below the static value).
<Page x:Class="ZoomTest.Page1" x:Name="page" xmlns="...">
xmlns:local="clr-namespace:ZoomTest"
local:AttachedProperties.Zoom="0.8">
<Grid />
</Page>
Now we have a Page that starts with a default zoom property of 80%. However, this does not do us much good. We don't actually tell the page how to zoom anywhere. This is where Binding comes into play.
<Page x:Class="ZoomTest.Page1" x:Name="page" xmlns="...">
xmlns:local="clr-namespace:ZoomTest"
local:AttachedProperties.Zoom="0.8">
<Grid LayoutTransform="{Binding Zoom, ElementName=page}">
</Grid>
</Page>
Now anything inside of the Grid will get a LayoutTransform based on the Zoom property of the Page! Unfortunately the LayoutTransform requires an actual Transform and not a double. Now we could have made the Zoom property a ScaleTransform, but that makes it less useful as an attached property. However, all is not lost:
public class ZoomConverter : IValueConverter
{
public object Convert(object value, Type targetType, object parameter, CultureInfo culture)
{
if (targetType != typeof(Transform))
throw new InvalidOperationException();

double val = Double.Parse(value.ToString()) / 100.0;
return new ScaleTransform(val, val);
}

public object ConvertBack(object value, Type targetType, object parameter, CultureInfo culture)
{
throw new NotSupportedException();
}
}
Now we just have to hook the converter up to the data binding, and viola! We have a Page who's Grid content zooms in and out with respect to a given scale.
<Page x:Class="ZoomTest.Page1" x:Name="page" xmlns="...">
xmlns:local="clr-namespace:ZoomTest"
local:AttachedProperties.Zoom="0.8">
<Page.Resources><local:ZoomConverter x:Key="zoomConverter" /></Page.Resources>
<Grid LayoutTransform="{Binding Zoom, ElementName=page, Converter={StaticResource zoomConverter}}">
</Grid>
</Page>
At this point all we have to do is wire up a Slider (two step process wraaa)!
<Window x:Class="GeometryTest.Window1" x:Name="window"
xmlns="..." local="clr-namespace:ZoomTest"
Title="Zoom Test" Height="480" Width="640">
<DockPanel LastChildFill="True">
<ToolBarTray DockPanel.Dock="Top">
<ToolBar>
<Label>Zoom:</Label><Slider x:Name="zoomSlider" Minimum="1" Maximum="100" Value="50" />
</ToolBar>
</ToolBarTray>
<Frame Source="Page1.xaml" LoadCompleted="ContentFrame_LoadCompleted" />
</DockPanel>
</Window>
...
void ContentFrame_LoadCompleted(object sender, NavigationEventArgs e)
{
Binding binding = new Binding();
binding.Source = zoomSlider;
binding.Path = new PropertyPath("Value");
(ContentFrame.Content as UIElement).SetBinding(AttachedProperties.ZoomProperty, binding);
}
Now, changing the zoom value with the Slider will cause the Grid to zoom in and out! Bonus points for adding a ScrollViewer to the Page to let you actually see the change in size of your Grid.