Saving space when drawing rectangles

Post your FreeBASIC source, examples, tips and tricks here. Please don’t post code without including an explanation.
jj2007
Posts: 2326
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Saving space when drawing rectangles

Post by jj2007 »

When drawing rectangles, Windows is unfortunately very wasteful: It uses the RECT structure to pass coordinates to the WinAPI calls. As everybody knows, screen resolution does not require DWORD size - there are no screens with 2 Billion pixels around.

In practice, WORD size would be sufficient: 65535 pixels at max, still difficult to achieve with current screens! Therefore, in order to save RAM, it would be extremely convenient if one could use the SMALL_RECT structure instead of the RECT structure.

Below a simple GUI application that uses the ultra-fast SmallRectToRect Subroutine to convert SMALL_RECTs to ordinary RECTs on the fly. There are not yet any timing routines implemented, but it should be easy to add. RAM usage can be monitored in Task Manager. WARNING: You will probably not see significant effects on speed and RAM usage for small element counts. Increase the #define to, say, ten Millions, and the effect on RAM usage, as compared to a traditional wasteful RECT array, should be really significant. Attention, it might not work with CPUs older than ten years.

Note this is Win32 only, although SmallRectToRect might work on Linux, too.

Code: Select all

#Include "windows.bi"
#define elements 20
Dim Shared smrc(0 To elements-1) As SMALL_RECT
Sub SmallRectToRect naked (pDest as RECT ptr, pSrc as SMALL_RECT ptr)
  asm
	#ifndef sMask
		.data
		.align 16
		sMask:
		.quad 0xffff0302ffff0100, 0xffff0706ffff0504
		.section .text  
	#endif
	mov eax, [esp+4]	' [pDest]
	mov edx, [esp+8]	' [pSrc]
	movlps xmm0, [edx]
	pshufb xmm0, sMask
	movups [eax], xmm0
	ret 4
  end asm
end sub

Function WndProc(hWnd As HWND, msg As  UINT, wParam As WPARAM, lParam As LPARAM) As LRESULT
  Dim As integer ct
  Dim As RECT rc
  Dim As PAINTSTRUCT ps
  Dim As HANDLE PtDC
  Select Case (msg)
  Case WM_PAINT
	PtDC=BeginPaint(hWnd, @ps)
	For ct=0 To elements-1
  		SmallRectToRect(@rc, @smrc(ct))
  		FrameRect(PtDC, @rc, GetStockObject(GRAY_BRUSH))
	Next
	EndPaint(hWnd, @ps)
  Case WM_KEYDOWN
  	if wParam=VK_ESCAPE then SendMessage(hWnd, WM_CLOSE, 0, 0)
  Case WM_SIZE
	GetClientRect(hWnd, @rc)
	For ct=0 To elements-1	' create the artwork
		smrc(ct).Left=Rnd*100+5
		smrc(ct).Top=Rnd*100+5
		smrc(ct).Right=smrc(ct).Left+Rnd*rc.right*0.666+10
		smrc(ct).Bottom=smrc(ct).Top+Rnd*rc.bottom*0.666+10
	Next 
  Case WM_DESTROY
      PostQuitMessage(0)
  End Select
  return DefWindowProc(hwnd, msg, wParam, lParam)
End Function

Function WinMain(hInstance As HINSTANCE, hPrevInstance As HINSTANCE, lpCmdLine As LPSTR, nShowCmd As Integer) As Integer
   Dim As WNDCLASSEX wc
   Dim As MSG msg
   Dim As string classname="FbGui"
   wc.cbSize = sizeof(WNDCLASSEX)
   wc.hbrBackground = COLOR_WINDOW+1
   wc.hCursor = LoadCursor(0, IDC_ARROW)
   wc.hIcon = LoadIcon(hInstance, IDI_APPLICATION)
   wc.hIconSm = wc.hIcon
   wc.hInstance = hInstance
   wc.lpfnWndProc = @WndProc
   wc.lpszClassName = StrPtr(classname)
   wc.style = CS_HREDRAW Or CS_VREDRAW
   RegisterClassEx(@wc)

   if CreateWindowEx(0, wc.lpszClassName, "Hello SMALL_RECT World",_
	WS_OVERLAPPEDWINDOW Or WS_VISIBLE, (GetSystemMetrics(SM_CXSCREEN) / 2) - 150,_
	(GetSystemMetrics(SM_CYSCREEN) / 2) - 150, 300, 300, 0, 0, hInstance, 0)=0 then
		    MessageBox(0, "Creating hMain failed miserably", 0, MB_OK)
		    return 0
   End If

   While GetMessage(@msg, 0, 0, 0)
      TranslateMessage(@msg)
      DispatchMessage(@msg)
   Wend

   return msg.wParam
End Function

WinMain(GetModuleHandle(NULL), NULL, COMMAND(), SW_NORMAL)
marcov
Posts: 3462
Joined: Jun 16, 2005 9:45
Location: Netherlands
Contact:

Re: Saving space when drawing rectangles

Post by marcov »

jj2007 wrote:When drawing rectangles, Windows is unfortunately very wasteful: It uses the RECT structure to pass coordinates to the WinAPI calls. As everybody knows, screen resolution does not require DWORD size - there are no screens with 2 Billion pixels around.
True, but instructions to load 32-bit values are shorter than to load 16-bit values, so it is less wasteful on processor prefetch resources.
(let alone conversion routines like you are proposing).
jj2007
Posts: 2326
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Saving space when drawing rectangles

Post by jj2007 »

You may be right, but I took my inspiration from the rect_t thread, which is going on and on, so I assume reducing RAM and disk use must be very important:
MrSwiss wrote:This is NOT for those thinking: "we have the memory, let's use it" (because, I don't agree, with that opinion).
...
But I'm willing to show, that a tiny type like above (shrunk to 4 Bytes size) is,
in fact all that is really needed, to put a simple rectangle to screen ...
marcov
Posts: 3462
Joined: Jun 16, 2005 9:45
Location: Netherlands
Contact:

Re: Saving space when drawing rectangles

Post by marcov »

jj2007 wrote:You may be right, but I took my inspiration from the rect_t thread, which is going on and on, so I assume reducing RAM and disk use must be very important:]
Code size eats up ram and disk too.
jj2007
Posts: 2326
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Saving space when drawing rectangles

Post by jj2007 »

marcov wrote:Code size eats up ram and disk too.
Absolutely: 20 bytes to call the converter, 26 for the converter itself, that's a whopping 46 bytes.
dodicat
Posts: 7983
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Saving space when drawing rectangles

Post by dodicat »

I think that is very nice code jj2007
dafhi
Posts: 1641
Joined: Jun 04, 2005 9:51

Re: Saving space when drawing rectangles

Post by dafhi »

i agree. had no idea ms had a small_rect type .. :o
dodicat
Posts: 7983
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Saving space when drawing rectangles

Post by dodicat »

Instead of the asm, perhaps:

Code: Select all

sub SmallRectToRect(byref pDest as rect ptr, pSrc as small_rect ptr)
       pdest->left=pSrc->left
       pdest->top=pSrc->top
       pdest->right=pSrc->right
       pdest->bottom=pSrc->bottom
end sub 
So it runs in 64 bit as well.
jj2007
Posts: 2326
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Saving space when drawing rectangles

Post by jj2007 »

dodicat wrote:So it runs in 64 bit as well.
My code doesn't run in 64-bit, that's true. Is there a switch or a constant that tells the compiler whether the source is 32- or 64-bit? Because your "true" FB code is obviously a bit more involved (@marcov: 69 bytes for the Sub alone):

Code: Select all

00401590            Ú$  55                   push ebp                         ; TmpFb.00401590(guessed Arg1)
00401591            ³.  89E5                 mov ebp, esp
00401593            ³.  53                   push ebx
00401594            ³.  8B45 0C              mov eax, [ebp+0C]
00401597            ³.  0FBF18               movsx ebx, word ptr [eax]
0040159A            ³.  8B45 08              mov eax, [ebp+8]
0040159D            ³.  8B08                 mov ecx, [eax]
0040159F            ³.  8919                 mov [ecx], ebx
004015A1            ³.  8B5D 0C              mov ebx, [ebp+0C]
004015A4            ³.  0FBF4B 02            movsx ecx, word ptr [ebx+2]
004015A8            ³.  8B5D 08              mov ebx, [ebp+8]
004015AB            ³.  8B03                 mov eax, [ebx]
004015AD            ³.  8948 04              mov [eax+4], ecx
004015B0            ³.  8B4D 0C              mov ecx, [ebp+0C]
004015B3            ³.  0FBF41 04            movsx eax, word ptr [ecx+4]
004015B7            ³.  8B4D 08              mov ecx, [ebp+8]
004015BA            ³.  8B19                 mov ebx, [ecx]
004015BC            ³.  8943 08              mov [ebx+8], eax
004015BF            ³.  8B45 0C              mov eax, [ebp+0C]
004015C2            ³.  0FBF58 06            movsx ebx, word ptr [eax+6]
004015C6            ³.  8B45 08              mov eax, [ebp+8]
004015C9            ³.  8B08                 mov ecx, [eax]
004015CB            ³.  8959 0C              mov [ecx+0C], ebx
004015CE            ³.  5B                   pop ebx
004015CF            ³.  89EC                 mov esp, ebp
004015D1            ³.  5D                   pop ebp
004015D2            À.  C2 0800              retn 8
... as compared to ...

Code: Select all

00401590            Ú$  8B4424 04            mov eax, [esp+4]                 ; TmpFb.00401590(guessed Arg1)
00401594            ³.  8B5424 08            mov edx, [esp+8]
00401598            ³.  0F1202               movlps xmm0, [edx]
0040159B            ³.  660F380005 10504000  pshufb xmm0, [405010]
004015A4            ³.  0F1100               movups [eax], xmm0
004015A7            À.  C2 0400              retn 4
fxm
Moderator
Posts: 12110
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Saving space when drawing rectangles

Post by fxm »

Example:

Code: Select all

#ifdef __FB_64BIT__
  Print "64";
#else
  Print "32";
#endif
Print "-bit code"
Print "Integer size: " & Sizeof(Integer) & " Bytes"

Sleep
dodicat
Posts: 7983
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Saving space when drawing rectangles

Post by dodicat »

Or I find easier to remember:

Code: Select all

#if sizeof(integer)=8
print "64"
#else
print"32"
#endif
sleep  
jj2007
Posts: 2326
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Saving space when drawing rectangles

Post by jj2007 »

Thanks, that was easy:

Code: Select all

Sub SmallRectToRect naked (pDest as RECT ptr, pSrc as SMALL_RECT ptr)
  asm
	#ifndef sMask
		.data
		.align 16
		sMask:
		.quad 0xffff0302ffff0100, 0xffff0706ffff0504
		.section .text  
	#endif
  #ifdef __FB_64BIT__
	movlps xmm0, [rdx]	' [pSrc]
	pshufb xmm0, sMask
	movups [rcx], xmm0	' [pDest]
	ret
  #else
	mov eax, [esp+4]	' [pDest]
	mov edx, [esp+8]	' [pSrc]
	movlps xmm0, [edx]
	pshufb xmm0, sMask
	movups [eax], xmm0
	ret 4
  #endif
  end asm
end sub
fxm
Moderator
Posts: 12110
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Saving space when drawing rectangles

Post by fxm »

dodicat wrote:Or I find easier to remember: ...
Or '#if sizeof(any ptr)=8' for an ultra purist!
(it's only a joke for someone) :-)
dodicat
Posts: 7983
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Saving space when drawing rectangles

Post by dodicat »

jj2007
Works well on both compilers.
Regarding
#ifdef __FB_64BIT__

Yea,
I shall remember
dash dash FB dash 64BIT dash dash
I have forgotten already.

rdx and rcx and the mmx registers I note for 64 bit.

Aside, non mmx cpu's don't work properly with fb since about version 18
I tested on my old Pentium pro a while back.

I think because you speak asm as a first language, many members will be interested in your posts.
But of course they won't admit it.
jj2007
Posts: 2326
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Saving space when drawing rectangles

Post by jj2007 »

dodicat wrote:I think because you speak asm as a first language, many members will be interested in your posts.
Actually, my first language was GfaBasic, a long time ago. But even then I spent a lot of time coding in (Motorola 68000) assembly, simply because GfaBasic was not fast enough (and at the time it was faster than most C dialects...).

This little thread, though, is dedicated to MrSwiss' Rect_t - optimized type definition thread:
MrSwiss wrote:This is NOT for those thinking: "we have the memory, let's use it" (because, I don't agree, with that opinion).
As you know, I do not always agree with our friend from Switzerland, but here I do! And how could I resist the temptation to optimise the dreadful and wasteful RECT problem? And it turns out that there is a simple solution! One SIMD instruction put to good use, and drawing rectangles is no longer a waste of memory. For example, drawing a Million rectangles needs now only 8 Megabytes instead of 16 - on my current machine, this saves roughly 0.1% of available memory. Not to mention the disk storage issue. So, if one day you want to draw a Million or more rectangles, dig out my code, open a bottle of good wine, and cheers ;-)
Post Reply