Monday, August 07, 2006

 

Blue angels we have heard on high

Quite a week at work here last week. The navy blue angels were here for seafair. With all the practice runs, I think productivity in the area was probably low. I know I spent my fair share of time gawking out my 17th floor window and admiring my tax dollars at work.

It looks like we may also finally get our house sold. We have a contract and are scheduled for closing on Aug 18, 2006. Cross your fingers and toes that it all goes well. I also checked in with my old group back in MD. It looks like they're about to disband and go their separate ways. And I wonder how John and family are doing on the Peru trip? I hope Montezuma didn't move in too soon.

Not much else here happening. But I've moved my blog to a more visible space. So this is probably going to be my last post here. I'll keep it cuz there's some good info here I may need again in the next few months. Check out my space over at http://sevenx7x.spaces.live.com/.

Friday, July 21, 2006

 

Visual Studio 2005 Solution Explorer Font Size, Or What do you mean "Icon?"

Large Monitor? Small Font? Solution explorer too hard to see in that tiny font. Looking for the visual studio setting to change the font size of solution explorer. Good Luck. In the "we don't really care" support department, "Aaron Brethorst" tells us that "by design" solution explorer uses the Desktop Icon font from your windows setting. At least you can change it. A compromise between added desktop waste and usability in the solution explorer.

https://connect.microsoft.com/feedback/ViewFeedback.aspx?FeedbackID=109160&SiteID=210

Tuesday, July 11, 2006

 

Prime Numbers

Wikipedia Prime Numbers was also very useful recently. As was this page about reversing a singly linked list.

 

Fast Bit Counting Routines

This seems to have vanished from its stanford site. Thought I'd archive it here for my reference. Very interesting concepts.

Fast Bit Counting Routines





Compiled from various sources by Gurmeet Singh Manku



A common problem asked in job interviews is to count the number of
bits that are on in an unsigned integer. Here are

seven solutions to
this problem. Source code in C is available.
























Iterated Count


int bitcount (unsigned int n)
{
int count=0;
while (n)
{
count += n & 0x1u ;
n >>= 1 ;
}
return count ;
}



Sparse Ones


int bitcount (unsigned int n)
{
int count=0 ;
while (n)
{
count++ ;
n &= (n - 1) ;
}
return count ;
}



Dense Ones


int bitcount (unsigned int n)
{
int count = 8 * sizeof(int) ;
n ^= (unsigned int) -1 ;
while (n)
{
count-- ;
n &= (n - 1) ;
}
return count ;
}



Precompute_8bit


// static int bits_in_char [256] ;

int bitcount (unsigned int n)
{
// works only for 32-bit ints

return bits_in_char [n & 0xffu]
+ bits_in_char [(n >> 8) & 0xffu]
+ bits_in_char [(n >> 16) & 0xffu]
+ bits_in_char [(n >> 24) & 0xffu] ;
}





Iterated Count runs in time
proportional to the total number of bits. It simply loops through
all the bits, terminating slightly earlier because of the while
condition. Useful if 1's are sparse and among the least significant
bits. Sparse Ones runs in time
proportional to the number of 1 bits. The line n &= (n - 1) simply
sets the rightmost 1 bit in n to 0. Dense
Ones
runs in time proportional to the number of 0 bits.
It is the same as Sparse Ones, except that it first toggles all bits
(n ~= -1), and continually subtracts the number of 1 bits from
sizeof(int). Precompute_8bit
assumes an array bits_in_char such that bits_in_char[i] contains the
number of 1 bits in the binary representation for i. It repeatedly
updates count by masking out the last eight bits in

n, and indexing
into bits_in_char.



Precompute_16bit


// static char bits_in_16bits [0x1u << 16] ;

int bitcount (unsigned int n)
{
// works only for 32-bit ints

return bits_in_16bits [n & 0xffffu]
+ bits_in_16bits [(n >> 16) & 0xffffu] ;
}




Precompute_16bit is a variant of
Precompute_8bit in that an array bits_in_16bits[] stores the number
of 1 bits in successive 16 bit numbers (shorts).



Parallel Count


#define TWO(c) (0x1u << (c))
#define MASK(c) (((unsigned int)(-1)) / (TWO(TWO(c)) + 1u))
#define COUNT(x,c) ((x) & MASK(c)) + (((x) >> (TWO(c))) & MASK(c))

int bitcount (unsigned int n)
{
n = COUNT(n, 0) ;
n = COUNT(n, 1) ;
n = COUNT(n, 2) ;
n = COUNT(n, 3) ;
n = COUNT(n, 4) ;
/* n = COUNT(n, 5) ; for 64-bit integers */
return n ;
}



Parallel Count carries out bit
counting in a parallel fashion. Consider n after the first line has
finished executing. Imagine splitting n into pairs of bits. Each
pair contains the number of ones in those two bit positions
in the original n. After the second line has finished executing,
each nibble contains the number of ones in those four bits
positions in the original n. Continuing this for five iterations,
the 64 bits contain the number of ones among these sixty-four bit
positions in the original n. That is what we wanted to compute.



Nifty Parallel Count


#define MASK_01010101 (((unsigned int)(-1))/3)
#define MASK_00110011 (((unsigned int)(-1))/5)
#define MASK_00001111 (((unsigned int)(-1))/17)

int bitcount (unsigned int n)
{
n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101) ;
n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ;
n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ;
return n % 255 ;
}



Nifty Parallel Count works the same
way as Parallel Count for the first three iterations. At the end of
the third line (just before the return), each byte of n contains the
number of ones in those eight bit positions in the original n. A
little thought then explains why the remainder modulo 255 works.



MIT HACKMEM Count


int bitcount(unsigned int n)
{
/* works for 32-bit numbers only */
/* fix last line for 64-bit numbers */

register unsigned int tmp;

tmp = n - ((n >> 1) & 033333333333)
- ((n >> 2) & 011111111111);
return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}



MIT Hackmem Count is funky.
Consider a 3 bit number as being 4a+2b+c. If we shift it right 1
bit, we have 2a+b. Subtracting this from the original gives 2a+b+c.
If we right-shift the original 3-bit number by two bits, we get a,
and so with another subtraction we have a+b+c, which is the number of
bits in the original number. How is this insight employed? The
first assignment statement in the routine computes tmp.
Consider the octal representation of tmp. Each digit in the
octal representation is simply the number of 1's in the corresponding
three bit positions in n. The last return statement sums
these octal digits to produce the final answer. The key idea is to
add adjacent pairs of octal digits together and then compute the
remainder modulus 63. This is accomplished by right-shifting
tmp by three bits, adding it to tmp itself and
ANDing with a suitable mask. This yields a number in which groups of
six adjacent bits (starting from the LSB) contain the number of 1's
among those six positions in n. This number modulo 63
yields the final answer. For 64-bit numbers, we would have to add
triples of octal digits and use modulus 1023. This is HACKMEM 169,
as used in X11 sources. Source: MIT AI Lab memo, late 1970's.



     No Optimization         Some Optimization       Heavy Optimization

Precomp_16 52.94 Mcps Precomp_16 76.22 Mcps Precomp_16 80.58 Mcps
Precomp_8 29.74 Mcps Precomp_8 49.83 Mcps Precomp_8 51.65 Mcps
Parallel 19.30 Mcps Parallel 36.00 Mcps Parallel 38.55 Mcps
MIT 16.93 Mcps MIT 17.10 Mcps Nifty 31.82 Mcps
Nifty 12.78 Mcps Nifty 16.07 Mcps MIT 29.71 Mcps
Sparse 5.70 Mcps Sparse 15.01 Mcps Sparse 14.62 Mcps
Dense 5.30 Mcps Dense 14.11 Mcps Dense 14.56 Mcps
Iterated 3.60 Mcps Iterated 3.84 Mcps Iterated 9.24 Mcps

Mcps = Million counts per second



Which of the several bit counting routines is the fastest? Results
of speed trials on an i686 are summarized in the table on left. "No
Optimization" was compiled with plain gcc. "Some
Optimizations" was gcc -O3. "Heavy Optimizations"
corresponds to gcc -O3 -mcpu=i686 -march=i686 -fforce-addr
-funroll-loops -frerun-cse-after-loop -frerun-loop-opt
-malign-functions=4
.





Thanks to Seth
Robertson
who suggested performing speed trials by extending href="bitcount.c">bitcount.c. Seth also pointed me to
MIT_Hackmem routine. Thanks to href="mailto:dennyrolling@hotmail.com"> Denny Gursky who
suggested the idea of Precompute_11bit. That would require three
sums (11-bit, 11-bit and 10-bit precomputed counts). I then tried
Precompute_16bit which turned out to be even faster.



If you have niftier solutions up your sleeves, please href="mailto:manku@cs.stanford.edu">send me an e-mail






Gurmeet Singh Manku

Last update: 27 Jul 2002

Monday, July 03, 2006

 

Some thought-provoking algorithmic questions.

Some interesting questions I've been asked recently along with my responses. Try to determine a fast and efficient way to provide the result of each situation.

Middle element of a singly linked list
Suppose you have a singly linked list of objects. How would you determine the object in the middle of the list using a single pass? One way: create 2 pointers. The first pointer traverses the list using the next pointer for each element. Every other time through the list the 2nd pointer is moved to the next element. When the 1st pointer reaches the end, the 2nd pointer is the middle.

Considerations: What if the list changes during the search and elements are added or removed?


Nth element from end of a singly linked list
Suppose you have the same list. How would you determine the 5th object from the end of the list? One way: Similar to the above except the 2nd pointer doesn't begin traversing until the 1st pointer gets to the 5th element. Then both pointers move until the 1st pointer again reaches the end. The 2nd pointer will point at the 5th element from the end.

Considerations: Same.

Sorting a file of integers
Suppose you have a file of integers. The size of the file is unknown. Each integer is in the range of 0 to 1000. How would you print the integers in sorted order? One way: create a 1000-element array. As each integer is read, use it as an index into the array and increment that element by 1. The array will hold a count of occurrences of each integer. At EOF, iterate over the 1000-element array and print the index of each non-zero cell using the value of the cell to tell how many times to print the index.

Considerations: file access security, buffers size, integer values within range

Find the start of a list
Suppose you have a array of integers. The array is sorted into ascending order except the starting point of the element is unknown. Find the 0-based index of lowest valued element in the array. For example, (20,30,5,10,15) returns 2. The array is a fixed, unlimited size. One way: Split the list in half. Compare the value of the left most element to the value midpoint element and compare the value of the midpoint element to the right most element. This comparison yields which half of the list contains the point where the numbers recycle. Update the left or right pointer to the mid point, reset to the new middle point. Repeat until left and right are adjacent. Compare the 2 values and return the index of the lower.

Considerations: locking the list from change, assuming list is sorted per specification, duplicates

Find a duplicate value
Suppose you have an array of integers. The size of the array is unlimited. Each cell in the array contains a value between 1 and the number of elements in the array. Find the value of any element that occurs more than once in the list. For example, (1,2,3,2,3) returns 2 or 3 but not 1. The list must remain intact when the function completes. One way: iterate through the list. Using the value of each cell as an index, negate the element (vals[Math.abs(vals[index])]) *= -1. If the element is already negative, it is a duplicate. Save the value. Revert all negatives values to positive.

Considerations: write access to target from called routine, locking list from change whilst executing.

Add an index to a very large data base table
You have a very high availability data base with a very large table that has a high frequency of inserts (10 per second). There are >400M rows in the table. You need to create a new index on the table with little to no downtime on the table. You cannot use create index because locking would stall access until it was able to complete. One way: Create a new table with the new index. Copy over all rows from the base table. Upon completion of the copy, rename the tables. Copy any rows that appeared between the end of your copy operation and the rename operation. Only a slight number of rows would receive an error. The application would be smart enough to wait a few seconds and retry.

The fox, the hen and the bag of corn.
A farmer has to cross a stream in a canoe. He has a fox, a hen and a bag of corn. He can only carry one item at a time with him across the stream in the canoe. If he leaves the fox alone with the chicken, the fox will eat the chicken. If he leaves the chicken alone with the corn, the chicken will eat the corn. How can he get everything across the stream in the least number of trips?

One way: Take the chicken across. Go back and get the fox. Leave the fox and take the chicken back to the original side. Leave the chicken on the original side and take the corn across. Go back and get the chicken.

 

Integrating SQL Server 2005 Reporting Services into an ASP.Net application

I recently had a chance to work with SQL Server 2005 Reporting services. I must say I'm fairly impressed with the offering. You can pull data from just about anywhere into a single place and then serve up reports in almost any format you want. Data from office docs (xl, word), XML files, just about any data base, flat files can be mushed together and served up in HTML, back to xl, PDF, and/or email formats.

I am integrating reports in an ASP.NET 2.0 application. The reports appear as another page inside the app with all of our menus, navigation, security and such wrapped around it. VS2005 includes a new data control called Report Viewer. Just set some properties and it serves up your report.

My only problem I had was in the deployment. Of course, everything works fine during development while everything is running on my local machine. The problem comes into play when the production environment is used where reporting services runs on a different machine from the web server. I was continually getting "The request failed with HTTP status 401" failure. Nothing in the IIS or Reporting Services log was helpful.

I eventually stumbled on a property of ServerReport called ReportServerCredentials. This was the secret element that eventually solved my problem. I found a sample on MSDN that got me most of the way there and it reminded me of this joke (scroll down to lost in space). It seems you can create a custom object to implement the IReportServerCredentials interface. The sample shows using forms authentication and a cookie. It turns out I what I wanted to use was the network credentials option instead. Using the debugger and trial and error, it seems that when have your custom object, reporting services first tries to use WindowsIdentity, then NetworkCredentials then GetFormsCredentials. WindowsIdentity returns a null value which appears to be a signal to try something else. GetFormsCredentials needs to return false after setting all of the out parameters to null. NetworkCredentials actually returns a System.Net.ICredentials object. I just created some properties in my web.config for ID and password.

On the report server machine, I added a local user and removed all logon rights. It's not the best security because the ID and password are in plain text in the file but there are other ways to work around that. So after 6 hours of research, I now have a fully functional report viewer integrated into my application.

Problem #2 was that I was getting my report rendered (i.e. I could see the little animation showing "generating report") but upon render, it never showed up in the HTML for the page. I did a quick web search and found some entries showing that if you set width and height to 100% that could cause the problem. I tried setting both to actual values (e.g. 400px). However, this caused scroll bars when the reports were larger than this.

A better fix seemed to be to change width and height back to 100% and set the viewer property AsyncRendering to false. Now the page takes a few extra seconds to display while the report is being retrieved but it correctly shows in the output.

All in all, I'd say I'm very happy with reporting services. Just a few little tweaks and maybe some better documentation would make it a fine tool.



Tweaked Sample implementation of IReportServerCredentials

///
/// custom objec to supply credentials for report server.
/// this implementation asks the utility for the ID and password
/// and relies on NetworkCredentials to login to the report server.
/// the ID configured must exist on the report server and be granted
/// access to execute the specified reports.
///
/// The ID should be denied "logon locally" access to prevent
/// misuse.
///
///

private class MyReportServerCredentials : IReportServerCredentials
{

public MyReportServerCredentials()
{
}

public WindowsIdentity ImpersonationUser
{
get
{
return null;
}
}

public System.Net.ICredentials NetworkCredentials
{
get
{
NetworkCredential nc = new NetworkCredential();
nc.UserName = ReportUtilities.ReportUserID;
nc.Password = ReportUtilities.ReportPassword;
return nc; // Using NetworkCredentials to authenticate.
}
}

public bool GetFormsCredentials(out System.Net.Cookie authCookie, out string user, out string password, out string authority)
{
authCookie = null;
user = password = authority = null;
return false; // do not use forms credentials to authenticate.
}
}


Sample call from ASP.NET page. Call from Page_Load() or other UI event method. This is a business layer routine that causes the report to be rendered in the output. Security checks are omitted from this method.

public static void Render(System.Web.UI.Page report, ReportViewer viewer)
{
string reportID = ID(report); // lookup path from query string

// perform security validation here

viewer.ServerReport.ReportServerUrl = ReportServerUrl; // property from web.config
viewer.ServerReport.ReportPath = ReportPath(reportID); // util function
viewer.ServerReport.ReportServerCredentials = new MyReportServerCredentials();
}

Call from ASP.Net code behind
protected void Page_Load(object sender, EventArgs e)
{
// Security Access check is performed by Render utility.
ReportUtilities.Render(this, this.Report);
}

Friday, June 30, 2006

 

Fixing up users and logins after restoring a SQL Server 2000 SS2K database data base

A slight flaw in SQL Server 2000 data base restore is in the handling of logins and users in the restored data base. If you backup a data base and restore it on a different machine or to a different name, the users and persmissions are not quite what you could hope for. So what's a poor schmuck to do?

sp_change_users_login @Action = 'Update_one', @UserNamePattern = 'user Id here', @LoginName = 'User ID here'

or something similar.

SS2k5 seems to have corrected this little flaw.

This scenario comes up in developer environments when data bases are copied frequently.

Thursday, June 01, 2006

 

You can take it with you

http://msdn.microsoft.com/coding4fun/inthebox/mobile2/default.aspx

Contains some interesting code so you can be notified when your NIC is online or enabled.
NIC disabled NIC Enabled Wireless Connection, etc.

Wednesday, May 10, 2006

 

Synaptics TouchPad coexisting with a real mouse

Like many of you, I have a Dell laptop with the built in touch pad from synaptics. I have a difficult time using my computer because the touch pad is sensitive and when I'm typing a long document, the touch pad would often detect a "click" and instantly reposition the cursor and my subsequent keystrokes into some random place in my document, or worse another application. I had a difficult time disabling this because when I installed the Microsoft Intellipoint drivers, they took over the PS/2 mouse drivers for the keypad as well as the actual mouse I wanted it to control. The Intellipoint drivers didn't offer any way to configure the touchpad and disable it or change any of the other settings?

So the big question: how to use the new mouse drivers but still disable the touch pad? The first part of the answer is to trash the little PS/2 adapter and plug the mouse straight into the USB port. Then open the mouse applet from control panel. You should see a tab labeled hardware. On that tab you should see a PS/2 device and a USB device. If you did step 1 as listed, then click on the PS/2 line, then click the Properties button. On the properties page, you should see a "driver" tab. On the driver properties page is a button labeled "Update driver…" Click that and then choose the synaptics driver for the device. You'll have to step through a few dialogs to get there. I downloaded the 8.something drivers before I started hoping they would solve the problem. Anyway, once you get the PS/2 device (the touchpad and touchstyk) under control of the synaptics driver, reboot and it looks like everything works ok. It's a little weird though because I disabled the pad altogether. I thought at first it wasn't working because until I get logged on and everything gets initialized, you can still use the touch pad. However, it eventually shuts off and starts ignoring all input. Now if I can just get the styk to stop drifting without resorting to cutting the cable … I typed this whole entry without a single phantom click so I'm pretty sure this is the right formula.

My new mouse is the Microsoft wireless Intellimouse Explorer 2.0. If only it had one of the cool little USB connectors that stored in the mouse, it would be the perfect mouse.

This page is powered by Blogger. Isn't yours?