hash_map creates access violation errors

hi,

I use a hash_map for storing 4x4 DCT-Blocks. Therefore I convert each block into a string looking like:
":-88:-3:-9:-91:-44:1:-7:-93:88:-1:9:42:-2:-2:-6:". Then I use the following code to identify blocks that have been seen before.

Code:

std::hash_map<std::string, int> blockMap; //initialize hash_map
...
// add blockString to hashmap:
if (blockMap[blockString] == NULL) {
   blockMap[blockString] = ++blockIDcounter;
   blockID = blockIDcounter;
} else {
   blockID = blockMap[blockString];
}

The blockIDcounter counts the number of different blocks.

during calculation of the first image frame, there is always a runtime error (access violation reading/writing to a certain address - its origniated somewhere in the hash_map-template) when reaching a blockIDcounter around 1800.

So, what could be the reason for this problem? I use Visual Studio C++ .NET 2003.


best regards,
Rebecca Hoffmann

>if (blockMap[blockString] == NULL) {
Two things: using NULL in anything but pointer context is very bad form, and using the [] operator to test if a key exists in a map container is not a good idea. The [] operator checks to see if the key exists, then adds it if it doesn't. You would be better off using the find() member function to see if a key exists.

I don't see anything wrong with that code. Can you supply more information about what you've found when debugging the problem? Is blockIDcounter always the same number at the time of the crash? What part of the hash_map code is causing the error? Is the string always the same when it crashes?

BTW, in .NET 2003, the hash_map is found in the stdext namespace, std::hash_map was deprecated by Visual C++. I'd be shocked if that was causing the error, but you might as well update your code.

Now I tried it in a somewhat different way:

Code:

// init hashtable for the dct blocks
typedef hash_map<string, int> hashtable;
typedef pair<string, int> blockPair;
hashtable blockMap;
hashtable::iterator mapIter; 

...

// add blockString to hashmap
mapIter = blockMap.find(blockString);		
if (mapIter == blockMap.end()) {
	blockMap.insert(blockPair(blockString, ++blockIDcounter));
	blockID = blockIDcounter;
} else {
	blockID = mapIter->second;
}

Explanation: blockString is generated from the AC-coefficients that are calculated using a live frame from a webcam. So everytime the values are different. The lenght of the blockstring varies but the longest one I have seen was 65 characters long.

The access violation errors are thrown every time at different positions in the frame (around the 2000th entry in the hashtable). The violation is thrown from different locations in the code: sometimes from "hash_compare" or "_Hash" (at the line: _Where = _List.insert(_Plist, _Val);) ...

it is very diversified :-)

My initial thought is that this crash doesn't have anything to do with the hash_map, that's just where it manifests itself. However, you'll need to do a lot more digging to find out what is going on. I will asume that you are running this through the VC++ 2003 debugger.

In the Exceptions window (Debug->Exceptions or Ctrl-Alt-E), the C++ Exceptions and Win32 Exceptions should be set to Break into the Debugger for the "When the exception is thrown:" option. This will make sure you are at the actual code that has the first problem.

When the exception is thrown, choose Break. Type "this" without the quotes in the Watch window and see what the memory address is (in the Value section). Also see what the type is (in the Type section). For example, this might be 0x000012e4 and the type std::list<std::pair<std::basic_string<char ... ... const, or something like that. If the value of this is 0x00000000 or 0x00000004 or something really small like that, then you are accessing a null pointer somewhere. If the number is larger and looks like a memory address, go to the memory window and enter in the address to see what the memory looks like. If it is FE EE FE EE or something like that, then chances are that the memory was already deleted. Keep poking around until you find out why it is crashing in that specific place, and hopefully that will give you clues about the real problem that is causing it to crash at all.

Then, use that information to figure out if you are doing something wrong in the code that uses the hash_map. For example, is the code you posted part of a class? Maybe the class instance was already destructed before this code was run because you are using a deleted pointer. Maybe you have an array of these classes and you accidentally accessed memory outside of the array bounds.

You need to keep digging and provide more information beyond the valid code snippets that you've posted so far. Otherwise, the only way somebody will be able to help you is if there is a known problem with the hash_map and they've seen it before.

Thank you, that hint helped me to search more efficiently (I am really not into VisualStudio)


Now I found out that low-level-function memcmp tries to access an address that contains nothing.

But what really annoys me is that the algorithm works well if I only run over half the image:

Code:

for (int line = 0; line < imgSize.height/2; line+=4){...}

So I suppose that there is a kind of overflow in the hash_map. Did I do anything wrong with the initialization?

Maybe it is easier to see, if I post the complete code:

Code:

void CCamShiftF::UseH264Q(IplImage* image) {


	// -- parameters --------------------------------------
	int quantFactor = 1;
	short fwdDctBlock[16] =  
	{
		1,  1,  1,  1, 
		2,  1, -1, -2, 
		1, -1, -1,  1, 
		1, -2,  2, -1
	};
	// ----------------------------------------------------


	// -- initialize variables and structures --
	unsigned char value8u;
	short value16s; 

	// init sizes
	CvSize imgSize;	// the size of the given image:
	imgSize.height = image->height;
	imgSize.width = image->width;

	CvSize blockImgSize;
	blockImgSize.height = imgSize.height/4;
	blockImgSize.width = imgSize.width/4;

	// init images:
	IplImage* pGrayImage = cvCreateImage(imgSize, IPL_DEPTH_8U, 1);
	int stepSize = pGrayImage->widthStep;
	IplImage* pBlockImage = cvCreateImage(blockImgSize, IPL_DEPTH_16S, 1);

	// init Arrays:
	short srcBlock[16] = {0};
	short tmpBlock[16] = {0};
	short dstBlock[16] = {0};

	// init hashtable for the dct blocks
	typedef hash_map<string, int> hashtable;
	typedef pair<string, int> blockPair;
	hashtable blockMap;
	hashtable::iterator mapIter; 
	string blockString = "";
	char* tmpStr = new char[5];

	int blockIDcounter = 0; // needed for indexing different blocks
	int blockID; // the ID of a specific block

	// -- apply conversions --
	cvCvtPixToPlane(image, pGrayImage, NULL, NULL, NULL); // get first channel only

	// -- main application loop --
	for (int line = 0; line < imgSize.height; line+=4) { 
		for (int column = 0; column < imgSize.width; column+=4) {
			
			// fill source Matrix:
			for (int mLine = 0; mLine < 4; mLine++) { 	
				for (int mColumn = 0; mColumn < 4; mColumn++) {		
					value8u = (unsigned char) *(pGrayImage->imageData + (line + mLine)*stepSize + column + mColumn); // get values from grayscale-image
					srcBlock[mLine*4 + mColumn] = (short) value8u; // needed because unsigned data is stored in signed char (imageData)
				}
			} // end of fill source matrix


			// -- apply transformation --

			// matrix multiplication (FwdDCT * Src = Temp): 
			for (int mLine = 0; mLine < 4; mLine++) {
				for (int mColumn = 0; mColumn < 4; mColumn++) {
					value16s = 0;
					for (int mElement = 0; mElement < 4; mElement++) {
						value16s += fwdDctBlock[mLine*4 + mElement] * srcBlock[mElement*4 + mColumn]; 
					} // end of element-loop
					tmpBlock[mLine*4 + mColumn] = value16s;
				} // end of column-loop		
			} // end of matrix multiplication
			
			// matrix multiplication (Temp * FwdDCT' = Dest): 
			for (int mLine = 0; mLine < 4; mLine++) {
				for (int mColumn = 0; mColumn < 4; mColumn++) {
					value16s = 0;
					for (int mElement = 0; mElement < 4; mElement++) {
						value16s += tmpBlock[mLine*4 + mElement] * fwdDctBlock[mColumn*4 + mElement];
					} // end of element-loop
					//debug// dstBlock[mLine*4 + mColumn] = value16s / 16; // ask Daidi about the / 16
					dstBlock[mLine*4 + mColumn] = value16s;
				} // end of column-loop		
			} // end of matrix multiplication

			dstBlock[0] = 0; // ignore DC-coefficient


			// -- apply quantization --
			for (int mLine = 0; mLine < 4; mLine++) { 	
				for (int mColumn = 0; mColumn < 4; mColumn++) {		

					value16s = dstBlock[mLine*4 + mColumn];
					
					value16s = value16s / quantFactor;
					//debug// value16s = value16s * quantFactor;
					value16s = value16s * quantFactor / 16;
				
					if (value16s > maxValue)
						maxValue = value16s;
					else if (value16s < minValue)
						minValue = value16s;			
				}
			} // end of quantization		


			// -- get block ID --

			// convert block to blockString:
			blockString = "";
			for (int element = 0; element < 16; element++) {
				if (dstBlock[element] != 0) {
					_itoa((int)dstBlock[element], tmpStr, 10);
					blockString = blockString += tmpStr;
				}
				blockString += ":";
			}

			// add blockString to hashmap
			mapIter = blockMap.find(blockString);
			if (mapIter == blockMap.end()) {
				blockMap.insert(blockPair(blockString, ++blockIDcounter));
				blockID = blockIDcounter;
			} else {
				blockID = mapIter->second;
			}

			*(pBlockImage->imageData + line*stepSize/4 + column) = blockID; // save blockID to block image
	
		} // end of line
	} // end of main application loop

	// -- tidy up --
	cvReleaseImage(&pBlockImage);
	cvReleaseImage(&pGrayImage);
	
}

> Now I found out that low-level-function memcmp tries to access an address that contains nothing.

This is good. More information about this would help. What does the call stack look like? what function is calling memcmp? Who sends that bad address to memcmp, which function sends that bad address to the function that sends the bad address to memcmp (and so on... where does the bad address originate from)? Is the hash_map itself bad? You can go to the Call Stack and double click on different functions in the stack to look at the variables at that level.

Also, I noticed that you have three arrays declared immediately before the hash_map. It is possible that if you overwrite the bounds of one of those arrays (probably dstBlock) that you will overwrite part of the data held by the hash_map. I didn't see any suspicious code with dstBlock, but that would make sense. Maybe try increasing the size of those arrays to a large number (like 100 or 1000). It shouldn't change how your code works, but it might rearrange the memory enough so that the hash_map isn't corrupted. I would try this first and if the crash doesn't happen, you can almost be sure that the problem is with overwriting the array.

Wow!

I just made this change:

Code:

//debug// short dstBlock[16] = {0};
short dstBlock[1000] = {0};

... and it works. I never would have expected something like that. Thank you very much!

Do you have an idea what could be the reason for this? Where do I write over the bounds of the dstBlock?

Honestly, I don't see where you do it. Obviously it doesn't happen very often since you say the crash doesn't happen until you've processed 1800-2000 times. I would definitely keep researching this and fix that problem even though it is "working" with the new array size. Consider stepping through the code, especially when the loop variables are at their highest, to see if you ever use an index higher than 16 for dstBlock. Like I said, I don't see it from looking at that code, but if you step through it you might be able to.

One option when you are debugging is to find the address of the dstBlock array and place that address in the Memory window. Each 2 digit hex number is a byte, so 16 shorts would be 32 numbers. Find the 33rd number (which should also be the address of the hash_map) and watch it to see when it changes (turns red) as you step through the code. Hopefully that will tell you where it is happening. Of course you'll want to ignore the times that it changes when the code is actually accessing the hash_map directly.