面试问题: Rotate a bitmap by 90 degrees

On August 9th, I posted the following problem on community.csdn.net, under VC/MFC 基础类:

Problem: Write code to generate a bitmap rotated 90 degrees clockwise from the original bitmap, without using any graphics library.

If you want to post your code here, write on your own, do not refer to anything else, no copy/paste, write your code here, review your code before submitting, and include how much time you spend. Add comments in English when possible.

I want to see who can give a good enough answer.

There have been lots of responses to this simple programming problem and some quite interesting discussions. Here is the link to the CSDN thread: http://community.csdn.net/Expert/topic/3254/3254627.xml?temp=.7896845

So here I'm going to comment on those responses.

hahu(地痞 -- 勿近) ( 两星(中级) )

#define WIDTHBYTES(bits) (((bits) + 31) / 32 * 4)

=>Global alloc bytes for destination bitmap....
long ldByteWidth = WIDTHBYTES(width*3);      
long ldByteHeight = WIDTHBYTES(height*3);
for(j = 0; j < height; j++)
{
   for(i = 0; i < width ;i++)
   {
       src = j*ldByteWidth + i*3;
       dst = i*ldByteHeight + j*3;
       memcpy(dst, src, sizeof(unsigned char)*3);
   }
}
Is it right? The byte count in this bitmap is ldByteWidth*height

This captures the essence of the problem quite well. Such quick thinking is essential in interviews. But the 'code' as it stands is just a simple sketch, far away from useable code.

ehom(？！) ( 四星(高级) )

//位图旋转，24位/32位
int rotated90(const char *filename)
{
 BITMAPFILEHEADER bmpfileheader;
 BITMAPINFOHEADER bmpinfoheader;
 fstream bmpfile;
 bmpfile.open(filename, ios::in|ios::out|ios::binary);
 if(!bmpfile) {
  return -1;
 }
 else {
  bmpfile.read((char *)&bmpfileheader, sizeof(bmpfileheader));
  if(bmpfileheader.bfType!=0x4D42) return -1;
  bmpfile.read((char *)&bmpinfoheader, sizeof(bmpinfoheader));
  if(bmpinfoheader.biBitCount!=24 && bmpinfoheader.biBitCount!=32) return -1;
 }
 //get depth 
 int bit = bmpinfoheader.biBitCount/8;      
 //get width of source bitmap
 int bmpWidth = bmpinfoheader.biWidth;
 //get height of source bitmap
 int bmpHeight = bmpinfoheader.biHeight;
 //set height of dest bitmap 
 bmpinfoheader.biHeight = bmpWidth;        
 //set width of dest bitmap
 bmpinfoheader.biWidth = bmpHeight;
 //set image size of dest bitmap 
 bmpinfoheader.biSizeImage = ((bmpHeight*bit-1)/4+1)*4*bmpWidth;
 //堆上开辟缓存区储存输出位图数据 
 char *buf = new char[bmpinfoheader.biSizeImage];
 //定义输出位图各行首地址数组 
 unsigned long *scanline = new unsigned long[bmpWidth]; 
 //get linesize of dest bitmap 
 int linesize=bmpinfoheader.biSizeImage/bmpWidth;
 unsigned long n=(unsigned long)&buf[0];         
 //获取输出位图各行在缓存区的首地址
 for(int i=bmpWidth-1;i>=0;i--) {
  scanline[i]=n;
  n+=linesize;                        
 }
 int m=(bmpWidth*bit)%4;
 if(m==0) {        
  for(int i=0;i   for(int j=0;j    bmpfile.read((char *)(scanline[j]+i*bit), bit);
   }                
  }
 }
 else {
  m=4-m;
  char *tempbuf=new char[m];
  for(int i=0;i   for(int j=0;j    bmpfile.read((char *)(scanline[j]+i*bit), bit);
   }
   bmpfile.read(tempbuf, m);
  }
 }
 //write head and image data 
 bmpfile.seekg(0);
 bmpfileheader.bfSize=bmpinfoheader.biSizeImage+sizeof(bmpfileheader)+sizeof(bmpinfoheader);
 bmpfile.write((char *)&bmpfileheader, sizeof(bmpfileheader));
 bmpfile.write((char *)&bmpinfoheader, sizeof(bmpinfoheader));
 bmpfile.write(buf, bmpinfoheader.biSizeImage);      
 bmpfile.close();
 delete[] buf;
 return 0;
}

time 10-20 mins

Apparently the author is an experienced programmer. But the code here solves a slightly different problem, it loads a bitmap from disk and writes back a rotated image. In interviews, you have to focus on the problem given to give the best answer, so you can't afford to work on anything else (like file I/O here). Also, what is required (implicitly) is to write reusable modular code, not a demo program.

yuliangpei(踏雪无痕) ( 二级(初级) )

int i,j;
for(i = 0; i < Width; i++)
{
    for(j = 0; j    {
       pDst[j][Width-i] = pSrc[i][j];
   }
}

其中，数据复制这一段不能直接用于程序，应该根据位图的bitCount而进行调整。程序是对应象素来写的。信手写的，不知对否？

Good understanding of the problem, far from complete usable code. Using two dimensional array notation is good for understanding the problem, but if you use that in your real code, it's less general or less efficient. One small mistake, Width - 1 - i should be used in place of Width -i.

ehom(？！) ( 四星(高级) )

#define getSize(width, height, depth) ((width*depth*3)/4)*4*height
 struct BitmapData
{
    int   width;
    int   height;
    void *pScan0; // pointer to first scanline
    int   bpp;    // bits per pixel 
    int   stride; // distance between scanlines
}; int rotated90(BitmapData bmpdata)
{
    if (bmpdata.bpp < 8) return -1;
 //bytes of depth 
 int depth=bmpdata.bpp/8;      
 //width of source bitmap 
 int bmpWidth=bmpdata.width;
 //height of source bitmap
 int bmpHeight=bmpdata.height;
 //image size of dest bitmap 
 int imagesize=getSize(bmpHeight, bmpWidth, depth);
 //堆上开辟缓存区储存输出位图数据 
 char *bufdst=new char[imagesize];
 //数组储存输出位图各行首地址 
 unsigned long *scanlinedst=new unsigned long[bmpWidth]; 
 //输出位图每行数据长度  
 int linesize=imagesize/bmpWidth;
 int n=(unsigned long)bufdst;         
 //获取输出位图各行在缓存区的首地址
 for(int i=bmpWidth-1;i>=0;i--) {
  scanlinedst[i]=n;
  n+=linesize;                        
 }
 
 char *buf=(char *)bmpdata.pScan0;
 int m=(bmpWidth*depth)%4;
 if(m!=0)m=4-m;
 for(int i=0;i  for(int j=0;j   memcpy((char *)(scanlinedst[j]+i*depth), buf, depth);
   buf+=depth;
  }
  buf+=m;
 }
 memcpy(bmpdata.pScan0, bufdst, imagesize);
 delete[] scanlinedst;
 delete[] bufdst; 
 return 0;
}
 
int openfile(const char *filename) // omitted

To ehom's second version, I said “Quite a few problems in ehon's code”. Here are they:

The function prototype int rotated90(BitmapData bmpdata) is wrong. The original problem askes you to generate a (new) rotated image from an existing image, there is no way a new image can be returned. bmpdata is passed as value type, it can't even modify an existing image to its rotated image. Rotate90 will be a better name.
bmpdata.bpp/8 does not handle bpp=15.
getSize, needs to check for multiplication overflow
No allocation failure check for new char[imagesize]
No allocation failure check for new unsigned long[bmpWidth]. This is also not needed. Also bmpWidth * sizeof(unsigned long) could overflow integer range.
memcpy inside nested loop is slow. Do not use that in performance critical code.
memcpy(bmpdata.pScan0, bufdst, imagesize) is dangerous, rotated image could be larger than original image because of scanline alignment.
scanlinedst and n, mixing pointers with integer will generate compile time error/warning. It does not work on 64-bit compiler, because int is still 32-bit while pointers are 64-bit.

holyeagle(一杯清茶) ( 一星(中级) )

#define GetImageSize(width,height,nCount) ((width*nCount+31)/32)*4*height 
#define OPENBMP(n) "d:\\bmp\\"#n".bmp"
#define SAVEBMP(n) "d:\\bmp\\"#n"R.bmp"

typedef struct tagRotateINfo
{
 INT  nWidth;
 INT  nHeight;
 VOID *pScan0; // pointer to first scanline
 INT  nBpp;  // bits per pixel 
 INT  nSrcStride; // distance between scanlines of Src
 INT  nDstStride; // distance between scanlines of dst
 VOID *pDst;  // pointer to destination 
}ROTATEINFO, *LPROTATEINFO;
 
BOOL CRotateImageDoc::Rotateclockwise90()
{
 // read image file
 CFile file;
 
 if (!file.Open(OPENBMP(1), CFile::modeRead) )
 {
  return FALSE;
 }
 
 // get file header
 BITMAPFILEHEADER FileHeader ={0};
 file.Read(&FileHeader, sizeof(BITMAPFILEHEADER));
 
 if (FileHeader.bfType != ((WORD) ('M' << 8) | 'B'))
 {
  return FALSE;
 }
 
 // get bitmap info
 DWORD dwBmpInfo = FileHeader.bfOffBits - sizeof(BITMAPFILEHEADER);
 DWORD dwRgb = dwBmpInfo - sizeof(BITMAPINFOHEADER);
 
 //apply memory
 LPBITMAPINFO pBmpInfo = (LPBITMAPINFO)new BYTE[dwBmpInfo];
 if (pBmpInfo == NULL)
 {
  file.Close();
  return FALSE;
 }
 memset(pBmpInfo, 0, sizeof(BYTE)*dwBmpInfo);
 
 file.Read(pBmpInfo, dwBmpInfo);
 if (pBmpInfo->bmiHeader.biBitCount >= 8 && pBmpInfo->bmiHeader.biCompression!=0)
 {
  file.Close();
  return FALSE;
 }
 
 // Get image data line by line
 DWORD dwWidth = pBmpInfo->bmiHeader.biWidth;
 DWORD dwHeight = pBmpInfo->bmiHeader.biHeight;
 WORD wBitCount = pBmpInfo->bmiHeader.biBitCount;
 
 DWORD dwSrcSize = GetImageSize(dwWidth, dwHeight, wBitCount);
 DWORD dwDstSize = GetImageSize(dwHeight, dwWidth, wBitCount);
 
 LPBYTE pSrcData = new BYTE[dwSrcSize];
 LPBYTE pDstData = new BYTE[dwDstSize];
 ASSERT(NULL != pSrcData && NULL != pDstData);
 ZeroMemory(pSrcData, sizeof(BYTE)*dwSrcSize);
 ZeroMemory(pDstData, sizeof(BYTE)*dwDstSize);
 
 DWORD dwColorTable = dwRgb/sizeof(RGBQUAD);
 RGBQUAD *pRgbQuad = new RGBQUAD[dwColorTable];
 ASSERT(NULL != pRgbQuad);
 ZeroMemory(pRgbQuad, dwRgb);
 
 // read
 LPBYTE lpTemp = pSrcData;
 INT nSrcStride = ((dwWidth*wBitCount+31)/32)*4;
 INT nDstStride = ((dwHeight*wBitCount+31)/32)*4;
 
 for (DWORD i = 0; i < dwHeight; ++i)
 {
  file.Read(lpTemp, nSrcStride);
  lpTemp += nSrcStride;
 }
 file.Seek(sizeof(BITMAPFILEHEADER) + sizeof(BITMAPINFOHEADER), CFile::begin);
 file.Read(pRgbQuad, dwRgb);
 
 file.Close();
 
 // set rotate infomation
 ROTATEINFO RoInfo = {0};
 RoInfo.nWidth = pBmpInfo->bmiHeader.biWidth;
 RoInfo.nHeight = pBmpInfo->bmiHeader.biHeight;
 RoInfo.pScan0 = pSrcData;
 RoInfo.pDst = pDstData;
 RoInfo.nBpp = pBmpInfo->bmiHeader.biBitCount;
 RoInfo.nSrcStride = nSrcStride;
 RoInfo.nDstStride = nDstStride;
 RotateImage(RoInfo);
 // store file
 CFile fileW;
 fileW.Open(SAVEBMP(1), CFile::modeCreate|CFile::modeReadWrite);
 // write head info
 fileW.Write(&FileHeader, sizeof(BITMAPFILEHEADER));
 // write bitmap info
 pBmpInfo->bmiHeader.biWidth = RoInfo.nHeight;
 pBmpInfo->bmiHeader.biHeight = RoInfo.nWidth;
 fileW.Write(pBmpInfo, dwBmpInfo);
 // write file data line by line
 lpTemp = (LPBYTE)RoInfo.pDst;
 for (i = 0; i < dwWidth; ++i)
 {
  fileW.Write(lpTemp, nDstStride);
  lpTemp += nDstStride;
 }
 fileW.Close();
 return TRUE;
}
BOOL CRotateImageDoc::RotateImage(ROTATEINFO RoInfo)
{
//////////////////////////////////////////////////////////////////////////
/* I just support above 8 bits image, 
 the bits of 1,2,4, I will convert to 24 bits at first, then do them as normal*/
//////////////////////////////////////////////////////////////////////////
 
 // get src prototype with color bits
 // if bpp is 8 bits, the step is one byte; if bpp is 16 bits, the step is two bytes, as soon on.
 INT nStep = RoInfo.nBpp / 8;
 INT nSrcStride = RoInfo.nSrcStride;
 INT nDstStride = RoInfo.nDstStride;
 INT nDiff = nSrcStride - RoInfo.nWidth*nStep;
 // check the src and dst are validate both.
 ASSERT(NULL != RoInfo.pScan0 && NULL != RoInfo.pDst);
 
 LPBYTE pSrcLine = (LPBYTE)RoInfo.pScan0, pDstLine = (LPBYTE)RoInfo.pDst;  //pointer to working line of Src & Dst buffer
 LPBYTE pSrcPixel = NULL, pDstPixel = NULL; //pointer to working pixel of Src & Dst buffer
 for (INT i = 0; i < RoInfo.nHeight; ++i)
 {
  pSrcPixel = pSrcLine + (nSrcStride - nStep - nDiff);
  pDstPixel = pDstLine;
  
  for (INT j = 0; j < RoInfo.nWidth; ++j)
  {
   memcpy(pDstPixel, pSrcPixel, nStep);
   pDstPixel += nDstStride;
   pSrcPixel -= nStep;
  }
  //get next line
  pSrcLine += nSrcStride;
  pDstLine += nStep;
 }
 
 return TRUE;
}
 
It taken me about three hours, too long!
Hope I can do it better next time.

Mostly similar problems, plus some new:

File IO is not required.
ROTATEINFO is not a good design, it mixes source bitmap with destination bitmap.
CFile, avoid using MFC when possible.
OPENBMP(1), write reusable code, not sample code, pass the file name as parameter
pBmpInfo and other memory allocation could be leaked.
GetImageSize could overflow.
ASSERT(NULL ! pSrcData && NULL != pDstData) is not valid, allocation could fail.
Bitmap could still be compressed.
RotateImage need runtime check for 1,2,4 bpp and when nBpp is not a multiple of 8.
memcpy is slow for performance critical code.

joysunstar(鹤鸣) ( 二级(初级) )

void Rotatebmp90() 
{

// this program rotate a 24bits-bitmap file by 90 degrees 
CFileDialog fileDlg(TRUE ,NULL,NULL ,NULL,"bitmap file(*.bmp)|*.bmp||") ;
if(fileDlg.DoModal() != IDOK )
 return ;

CString strFileName = fileDlg.GetPathName() ;
CFile bmpFile(strFileName,CFile::modeRead) ;
BITMAPFILEHEADER bmfh ;

bmpFile.Read(&bmfh,sizeof(BITMAPFILEHEADER) ) ;
if(bmfh.bfType != 0x4d42 )
 return ;
BITMAPINFOHEADER bmih ;
bmpFile.Read(&bmih,sizeof(BITMAPINFOHEADER)) ;
if(bmih.biBitCount != 24)
{
     AfxMessageBox("not a true color image !",MB_ICONINFORMATION) ;
     return ;
}
      
bminfo->bmiHeader = bmih ;
bmNewInfo->bmiHeader = bmih ;

DWORD width = bmih.biWidth ;
DWORD height = bmih.biHeight ;
DWORD offwidth = (width + 3) & ~3 ;
DWORD offHeight = (height + 3) & ~3 ;

bmNewInfo->bmiHeader.biHeight = width ;
bmNewInfo->bmiHeader.biWidth = height ;
bmNewInfo->bmiHeader.biSizeImage = offHeight * width * 3 ;

m_ImgWidth = width ;
m_ImgHeight = height ;

if(lpSrc)
{
free(lpSrc) ;
lpSrc = NULL ;
}
if(lpDest)
{
free(lpDest) ;
lpDest = NULL ;
}
 lpSrc = (LPBYTE)malloc(bmih.biSizeImage) ;
 lpDest = (LPBYTE)malloc(width * offHeight * 3) ;
 ZeroMemory(lpDest,width * offHeight * 3) ;

 bmpFile.Read(lpSrc,bmih.biSizeImage) ;

 BYTE *pixel ;
 
 for(DWORD i = 0 ; i < height ;i++)
 {
 for(DWORD j = 0 ;j < width ;j++)
 {
 pixel = lpSrc + i * offwidth * 3 + j * 3;      
 *(lpDest + j * offHeight * 3 + (height - i) * 3) = *pixel; 
 *(lpDest + j * offHeight * 3 + (height - i) * 3 + 1) = *(pixel + 1 ) ; 
 *(lpDest + j * offHeight * 3 + (height - i) * 3 + 2) = *(pixel + 2 ); 
 }

 }
 bmpFile.Close() ;

 UpdateAllViews(NULL) ;
}

File selection dialog box and file I/O is not required.
Where is bminfo and bmNewInfo declared?
offHeight * 3 is not the same as (height * 3 + 3 ) /4 * 4
biSizeImage could overflow.
Where is lpSrc and lpDest declared? Member variable of the class?
The code within the nested loop is really slow.

ALNG(?) ( 一级(初级) )

// start at 9:30
// Define a struct or class to store information about a bitmap:

struct BitmapInfo
{
public:
 // Ctors, Detors, skipped
 /// @brief rotate @c *this 90 degree clockwise.
 ///
 void rotate90Clockwise();
private:
 int    width;
 int    height;
 void * pScan0;   // pointer to first scanline
 int    bpp;      // bits per pixel 
 int    stride;   // distance between scanlines
private:
 /// @brief: internally used to get byte width of a scanline
 inline unsigned lineWidth()const{ return stride;  }
 
 /// @brief: offest of specified pixel from base address
 inline unsigned pixelOffest(unsigned row, unsigned col)const{
  return  row*lineWidth() + col*bbp;
 }

 /// @brief: internally used helper function to get the address
 /// of the pixel at row and col
 /// @param row row of the specified pixel, count from 0
 /// @param col col of the specified pixel, count from 0.
 /// @return address of the specified pixel
 inline char * pixel(unsigned row, unsigned col)const{
  return reinterpret_cast(pScan0)+ pixelOffset(row,col);
 }
 
 /// @brief: internally used to copy a pixel from @c from to @c to
 inline void copyPixel(const char * from, char * to)const{
  for(unsigned i=0; i   to[i]=from[i];
 }

};

// 11 12 13 14 
// 21 22 23 24
// 31 32 33 34
// ==>
// 31 21 11
// 32 22 12
// 33 23 13
// 34 24 14
//
// should be possible to work out a O(1) space complexity algorithm
// here I use the plain O(widht*height) one
//
// a quick but less smart solution
//

void BitmapInfo::rotate90Clockwise()
{
 BitmapInfo tmp(*this); // make a copy 
 
 height = width;
 width = tmp.height;
 // set stride properly.
 
 // do the actual rotation
 for(unsigne r=0; r  for(unsigned c=0; c   copyPixel( tmp.pixel(r,c), pixel(c,width-r-1);

Should BitmapInfo be a class, instead of a struct?
Quite a few mixing of unsigned with int.
Critical BitmapInfo copy constructor skipped.
Rotated image may be larger than original image in space because of scanline alignment. Simply switching height and width does not give you rotated image, stride may be wrong after that.
copyPixel copies source pixels into tmp bitmap, which is then thrown away?
The rotating loop is slow, you're trusting compiler to be able to do all the optimizations.
Not a single error check.

ambochan(打杂) ( 五级(中级) )

Lots of NT GDI calls

Does not meet requirement. Do not use any graphics library.

Your job could be to implement those graphics library, not using it as an application programmer.

huanyun(无妻徒刑) ( 两星(中级) )

typedef struct tagXIMGDATA
{
 int    width;
 int    height;
 void * pScan0;   // pointer to first scanline
 int    bpp;      // bits per pixel 
 int    stride;   // distance between scanlines
} XIMGDATA;

void FreeImg(XIMGDATA& ImgDst)
{
 if(ImgDst.pScan0 != NULL) 
 {
  delete [] ImgDst.pScan0;
  ImgDst.pScan0 = NULL;
  ImgDst.width  = 0;
  ImgDst.height = 0;
  ImgDst.bpp    = 0;
  ImgDst.stride = 0;
 }
}

int RotateImg(XIMGDATA& ImgDst,const XIMGDATA& ImgSrc)
{
 int nRet = -1;
 FreeImg(ImgDst);

 int nWidthS  = ImgSrc.width;
 int nHeightS = ImgSrc.height;
 int nWidthD  = nHeightS;
 int nHeightD = nWidthS;
 int nBitCount = ImgSrc.bpp;
 int nRowLenSrc = ImgSrc.stride;
 BYTE* pSrc = static_cast(ImgSrc.pScan0);
 if (nWidthS < 1 || nHeightS < 1 
  || nWidthS > 10000 || nHeightS > 10000
  || nBitCount < 1 || nBitCount > 64 
  || nRowLenSrc < 0 ||  pSrc == NULL) 
  return nRet;

 int nRowLenDst = nWidthD * nBitCount / 8;
 if (nBitCount == 1 && nWidthD % 8) ++nRowLenDst;
 nRowLenDst =  ((nRowLenDst + 3) & ~3); 
 
 BYTE *pDst = new BYTE[nHeightD*nRowLenDst];
 if(pDst == NULL)
 {
  FreeImg(ImgDst); 
  return nRet;
 }
 memset(pDst, 0, nHeightD*nRowLenDst);
 ImgDst.pScan0 = static_cast(pDst);
 ImgDst.width  = nWidthD;
 ImgDst.height = nHeightD;
 ImgDst.bpp    = nBitCount;
 ImgDst.stride = nRowLenDst;

 int i,x,y,nPosS=0,nPosD=0;
 int nPixelByte = ImgDst.bpp>>3;
 BYTE bMaskD,bMaskS;
 switch(nBitCount)
 {
 case 1:
  for(y=0;y  {
   nPosD =  nRowLenDst*y;
   nPosS =  y>>3;
   bMaskD = static_cast( 0x80 );
   bMaskS = static_cast( 0x80 >> (y % 3) );
   x = 0;
   while(x < nWidthD)
   {
    if(pSrc[nPosS] & bMaskS)
    {
     pDst[nPosD] |= bMaskD;
    }
    ++x;
    bMaskD >>=1;
    nPosS  += nRowLenSrc;
    if(bMaskD == 0) 
    {
     bMaskD=0x80;
     ++nPosD;
    }
   }
   for(x=0;;++x)
   {
    pDst[nPosD] = pSrc[nPosS];
    nPosD += nPixelByte;
    nPosS += nRowLenSrc;
   }
  }
  nRet = 0;
  break;
 case 8:
 case 16:
 case 24:
 case 32:
  for(y=0;y  {
   nPosD = nRowLenDst*y;
   nPosS = y*nPixelByte;
   for(x=0;x   {
    for(i=0;i    {
     pDst[nPosD+i] = pSrc[nPosS+i];
    }
    nPosD += nPixelByte;
    nPosS += nRowLenSrc;
   }
  }
  nRet = 0;
  break;
 default:
  break;
 }
 return nRet;
}

Why not use a class? Then FreeImg and RotateImg will just be member functions.
Missing important constructor, at least to set pScan0 to NULL.
delete [] ImgDst.pScan0, pScan0 is void pointer.
pSrc can be const pointer.
Checking for nWidthS, nHeightS larger than 10000 is good, but too restrictive.
Checking for nBitCount > 64 is too restrictive, GDI+ supports ARGB 16-bit per channel images
nRowLenSrc could be negative for bottom-up images.
Why ++nRowLenDst?
Check for nHeightD * nRowLenDst overflow
For each pixel writing to destination using pDst[nPosD] |= bMaskD is slow.
Why for (x=0;;++x)? When does it end?
Slow rotating loop.

tuqvb(风间苍月) ( 一级(初级) )

// ***********************************************************
// ohoh, only a kernel function
// time: 30 min
// ***********************************************************
// PixelS_Type  : type of source image pixel
// PixelD_Type  : type of dest image pixel
// wid          : width of source image and height of dest image, in pixel
// hei          : height of source image and width of dest image, in pixel
// psrc         : address of first pixel of source image
// lPitchSrc    : the length of source scan line, in bytes
// pdst         : address of first pixel of dest image
// lPitchDst    : the length of dest scan line, in bytes
// note         : there must be a convert from source to dest

template
void Ration90(int wid, int hei,
  const PixelS_Type *psrc, int lPitchSrc, 
  PixelD_Type *pdst, int lPitchDst)
{
 char *plsrc= reinterpret_cast(const_cast(psrc));  // scanline address of source
 int xdoffset= (hei - 1) * sizeof(PixelD_Type);     // pixel address offset of dest
 for (int y= 0; y < hei; ++y)
 {
  char *pldst= reinterpret_cast(pdst);    // scanline address of dest
  int xsoffset= 0;       // pixel address offset of source
  for (int x= 0; x < wid; ++x)
  {
   // movx dst[x][hei - 1 - y], src[y][x]
   *reinterpret_cast(pldst + xdoffset)= 
    *reinterpret_cast(plsrc + xsoffset);
   pldst+= lPitchDst;
   xsoffset+= sizeof(PixelS_Type);
  }
  plsrc+= lPitchSrc;
  xdoffset-= sizeof(PixelD_Type);
 }
}

// ***********************************************************
// use sample
typedef short PIXEL555;
typedef unsigned short PIXEL565;
typedef int PIXEL32;

typedef struct _stPixel24
{
 char r;
 char g;
 char b;

 _stPixel24& operator= (PIXEL32 p32){ return *this;}
 _stPixel24& operator= (PIXEL555 p16){ return *this;}
 _stPixel24& operator= (PIXEL565 p16){ return *this;}

 operator PIXEL32(void){ return 0;}
 operator PIXEL555(void){ return 0;}
 operator PIXEL565(void){ return 0;}
}PIXEL24;

#define WIDTH 83
#define HEIGHT 85

PIXEL24 image24[WIDTH][HEIGHT];

PIXEL32 image32[HEIGHT][WIDTH];
PIXEL565 image565[HEIGHT][WIDTH];
PIXEL555 image555[HEIGHT][WIDTH];

Ration90(WIDTH, HEIGHT, &image32[0][0], WIDTH * sizeof(PIXEL32), &image24[0][0], HEIGHT * sizeof(PIXEL24));
Ration90(WIDTH, HEIGHT, &image565[0][0], WIDTH * sizeof(PIXEL565), &image24[0][0], HEIGHT * sizeof(PIXEL24));
Ration90(WIDTH, HEIGHT, &image555[0][0], WIDTH * sizeof(PIXEL555), &image24[0][0], HEIGHT * sizeof(PIXEL24));

Ration90(HEIGHT, WIDTH, &image24[0][0], WIDTH * sizeof(PIXEL24), &image32[0][0], HEIGHT * sizeof(PIXEL32));
Ration90(HEIGHT, WIDTH, &image24[0][0], WIDTH * sizeof(PIXEL24), &image565[0][0], HEIGHT * sizeof(PIXEL565));
Ration90(HEIGHT, WIDTH, &image24[0][0], WIDTH * sizeof(PIXEL24), &image555[0][0], HEIGHT * sizeof(PIXEL555));

Finally, someone thought about using template!! I acutally used template in production code (part of Avalon code). But you should at least explain why did you choose to use template. The benefit of using template is to avoid memcpy in the inner loop. The binary code generated will be larger, but it will be much faster, because each instantiation will be for a constant color depth. Compiler will be able to generate the minimum code for that case.

pldst and xdoffset can be merged into a single variable.
plsrc and xoffset can be merged into a single variable.
Code is not complete. The problem is to write (generic) code to generate a rotated image from an image.

To be fair, here is my code

FengYuanMSFT

class Image
{
public:
    int m_width;
    int m_height;
    int m_bpp;
    int m_stride;
    void * m_pScan0;
 
    Image()
    {
        m_pScan0 = null;
    }
 
    ~Image()
    {
        if (m_pScan0)
        {
            delete [] (char *) m_pScan0;
            m_pScan0 = null;
        }
   }
 
   Image * Rotate90() const;
};
 template<typename Pixel>
Rotate(Image * pDst, const Image * pSrc)
{
    for (int y = 0; y < pDst->m_height; y ++)
    {
        const Pixel * pS = (Pixel *) ((char *) pSrc->m_pScan0 + (pSrc->m_Height - 1) * pSrc->Stride) + y;
              Pixel * pD = (Pixel *) ((char *) pDst->m_pScan0 + y * pDst->stride);
 
        for (int x = 0; x < pDst->m_width; x ++)
        {
            * pD ++ = * pS;
            pS = (Pixel *) ((char *) pS - pSrc->m_Stride);
        }
    }
}
 #pragma pack(push, 1)
typedef struct { char one; char two; char three; } triple;
#pragma pack(pop)
 
Image * Image::Rotate90() const
{    // Parameter validation
    if (m_width < 0 || (m_height < 0) || (m_bpp < 1))
    {
        return null;
    }
 
    if (((MAX_INT-31) / m_bpp) < m_height) // avoid overflow
    {        return null;
    }
 
    int stride = (m_height * m_bpp + 31) / 32 * 4; // dword align
    
    if ((MAX_INT / stride) < m_width) // avoid overflow
    {        return null;
    }
 
    Image * pResult = new Image();
 
    if (pResult == null)
    {
         return null;
    }
 
    pResult->m_width  = m_height;
    pResult->m_height = m_width;
    pResult->m_bpp    = m_bpp;
    pResult->m_stride = stride;
    pResult->m_Scan0  = new char[stride * m_width];
 
    if (pResult->m_Scan0 == null)
    {
        delete pResult;
        return null;
    }
 
    switch (m_bpp)
    {
        case 8:
            Rotate<char>(pResult, this); break;
 
        case 15:
        case 16:
            Rotate<short>(pResult, this); break;
 
        case 24:
            Rotate<triple>(pResult, this); break;
 
        case 32:
            Rotate<long>(pResult, this); break;
 
        case 64:
            Rotate<double>(pResult, this); break;
 
        default:
            assert(false); // new image format
            delete pResult;
            pResult = null;
    }
 
    return pResult;}

Some explanations:

It's OK to write a simple solution using memcpy or a loop to copy each pixels. But you need to understand that such a solution is considered slow for a high performance graphics library. For 1000 x 1000 pixel image, the inner loop will be executed 1 million times.
memcpy has two implementations: one inline implementation and one out-of-line function implementation. The inline version should be faster for small data size, the out-of-line implementation is optimized for copying large amount of data.
memcpy is considered slow here because the size parameter is a variable, so compiler/runtime library has to use a loop to implement it. Any loop or conditional jump is considered slow in such an inner loop.
Using template is faster here because each instance of the template knows its pixel size as a constant, so copying a pixel can be implemented in a single instruction for 8-bpp 15-bpp, 16-bpp, 32-bpp images, much faster than a loop.
Checking for multiplication overflow is essential to avoid heap buffer overrun which could result in security risks.
The code here is not compiled, nor tested.

Thanks for all the replies.

打印 | 张贴于 2004-08-18 02:27:00 | Tag:暂无标签

留言反馈

#re: Rotate a bitmap by 90 degrees 编辑

if
BitCount%8==0;
we could to transfort pixels data in loop in memory;1Pixel once;
but when BitCount%8!=0,CPU will be much used

Now I see GDI is good.

2007-11-10 12:12:00 | [匿名:Kuikui]