 |
Das deutsche QBasic- und FreeBASIC-Forum
Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
|
| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
UEZ
Anmeldungsdatum: 24.06.2016
Beiträge: 147
Wohnort: Opel Stadt
|
 Verfasst am: 15.12.2017, 01:17 Titel: Absturz bei großen Bilden (nur Windows) |
 |
|
Hallo,
kann jemand mir sagen, warum bei größeren Bildern die Exe abstürzt (Speicherschutzverletzung)?
| Code: |
'coded by UEZ build 2017-12-15
#define WIN_INCLUDEALL
#include Once "windows.bi"
#Include Once "win/gdiplus.bi"
#include Once "string.bi"
Using GDIPLUS
Declare Function FileOpenDialog (Byref sTitle As String, Byref sDir As String = CurDir, sFilter As String = !"All Files (*.*)" + Chr(0) + "*.*" + Chr(0, 0)) As String
Declare Function _GDIPlus_ImageCountColors32(himage as any Ptr) as uInteger
Declare Function _GDIPlus_ImageCountColors24(himage as any Ptr) as UInteger
Declare function _GDIPlus_ImageCountColorsAccurat(himage as any Ptr) as uInteger
Declare function _GDIPlus_ImageCountColors24ASM(himage as any Ptr) as uInteger
Declare Function _GDIPlus_ImageGetPixelFormat(hImage as any ptr) as UInteger
Declare Sub Quicksort(Array() As uinteger, iStart As uinteger, iEnd As uinteger)
Declare Sub RadixSortUInt32(a() as UInteger, pa as UByte = 1)
Function _GDIPlus_ImageCountColors32(himage as any Ptr) as uInteger 'slower variant but full 32-bit support
Dim As Single iW, iH, iPixel, iRowOffset
GdipGetImageDimension(hImage, @iW, @iH)
Dim As BitmapData tBitmapData
Dim As Rect tRect = Type(0, 0, iW - 1, iH - 1)
Dim as uinteger aColors(0 to iW * iH), c = 0, iX, iY
? "Image dimension: " & iW & "x" & iH
? "Counting all 32-bit colors"
_GDIPlus_ImageGetPixelFormat(hImage)
GdipBitmapLockBits(hImage, Cast(Any Ptr, @tRect), ImageLockModeRead, PixelFormat32bppARGB, @tBitmapData)
For iY = 0 To iH - 1
iRowOffset = iY * iW
For iX = 0 To iW - 1
aColors(c) = Cast(uInteger Ptr, tBitmapData.Scan0)[iRowOffset + iX]
c += 1
Next
Next
GdipBitmapUnlockBits(hImage, @tBitmapData)
? "Sorting color array"
RadixSortUInt32(aColors())
? "Counting unique colors"
c = 0
For iY = 0 to Ubound(aColors) - 2
If aColors(iY) < aColors(iY + 1) Then c += 1
Next
Return c
End Function
Function _GDIPlus_ImageCountColors24(himage as any Ptr) as uInteger
Dim As Single iW, iH, iPixel, iRowOffset
GdipGetImageDimension(hImage, @iW, @iH)
Dim As BitmapData tBitmapData
Dim As Rect tRect = Type(0, 0, iW - 1, iH - 1)
Dim as uInteger c = 0, iX, iY
Dim as UlongInt iColor
Dim as Ubyte aColors()
Redim aColors(0 to 256^3 + 1)
? "Image dimension: " & iW & "x" & iH
? "Counting all 24-bit colors"
GdipBitmapLockBits(hImage, Cast(Any Ptr, @tRect), ImageLockModeRead, PixelFormat32bppRGB, @tBitmapData)
For iY = 0 To iH - 1
iRowOffset = iY * iW
For iX = 0 To iW - 1
iColor = Cast(uInteger Ptr, tBitmapData.Scan0)[iRowOffset + iX] and &h00FFFFFF 'read and make color value 24-bit
If aColors(iColor) = 0 Then
c += 1
aColors(iColor) = 1
Endif
Next
Next
GdipBitmapUnlockBits(hImage, @tBitmapData)
Return c
End Function
function _GDIPlus_ImageCountColorsAccurat(himage as any Ptr) as uInteger 'very very slow!
Dim As Single iW, iH, iPixel, iRowOffset
GdipGetImageDimension(hImage, @iW, @iH)
Dim As BitmapData tBitmapData
Dim As Rect tRect = Type(0, 0, iW - 1, iH - 1)
Dim as uinteger aColors(0 to iW * iH), iColor, c = 0, p = 0, iX, iY, iYY
Dim as Boolean bFound
? "Image dimension: " & iW & "x" & iH
? "Counting all 32-bit colors"
_GDIPlus_ImageGetPixelFormat(hImage)
GdipBitmapLockBits(hImage, Cast(Any Ptr, @tRect), ImageLockModeRead, PixelFormat32bppARGB, @tBitmapData)
For iY = 0 To iH - 1
iRowOffset = iY * iW
For iX = 0 To iW - 1
iColor = Cast(uInteger Ptr, tBitmapData.Scan0)[iRowOffset + iX]
bFound = False
For iYY = 0 to p
If iColor = aColors(iYY) Then
bFound = true
Exit For
End If
Next
If Not bFound then
aColors(p) = iColor
p += 1
c += 1
End if
Next
Next
GdipBitmapUnlockBits(hImage, @tBitmapData)
Return c
End Function
Function _GDIPlus_ImageCountColors24ASM(himage as any Ptr) as uInteger
Dim As Single iW, iH, iPixel
GdipGetImageDimension(hImage, @iW, @iH)
Dim As BitmapData tBitmapData
Dim As Rect tRect = Type(0, 0, iW - 1, iH - 1)
Dim as uInteger c = 0, iX, iY, iPixels = iW * iH
Dim as Byte aColors()
Redim aColors(0 to 256^3 + 1)
? "Image dimension: " & iW & "x" & iH
? "Counting all 24-bit colors"
GdipBitmapLockBits(hImage, Cast(Any Ptr, @tRect), ImageLockModeRead, PixelFormat32bppARGB, @tBitmapData)
Dim As Dword Ptr pBmp = Cast(Any Ptr, tBitmapData.scan0)
Dim As Byte Ptr pColors = @aColors(0)
Asm
mov esi, [pBmp]
mov ecx, [iPixels]
mov edi, [pColors]
Xor eax, eax
_Pixel_Count:
mov ebx, [esi]
and ebx, &hFFFFFF
cmp Byte Ptr [edi + ebx], 1
je _Next
add eax, 1
mov Byte Ptr [edi + ebx], 1
_Next:
add esi, 4
sub ecx, 1
jnz _Pixel_Count
mov [c], eax
End Asm
GdipBitmapUnlockBits(hImage, @tBitmapData)
Return c
End Function
Function _GDIPlus_ImageGetPixelFormat(hImage as any ptr) as UInteger
Dim as UInteger iFormat
GdipGetImagePixelFormat(hImage, @iFormat)
Return iFormat
End Function
'https://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Quicksort
Sub Quicksort(Array() As uinteger, iStart As uinteger, iEnd As uinteger)
Dim As uInteger i = iStart, j = iEnd, iPivot = Array((i + j) Shr 1)
While i <= j
While Array(i) > iPivot
i += 1
Wend
While Array(j) < iPivot
j -= 1
Wend
If i <= j Then
Swap Array(i), Array(j)
i += 1
j -= 1
End if
Wend
If j > iStart Then Quicksort(Array(), iStart, j)
If i < iEnd Then Quicksort(Array(), i, iEnd)
End Sub
Sub RadixSortUInt32(a() as UInteger, pa as UByte = 1)
Dim as UInteger aBucket(0 to Ubound(a), 0 to 10), i, x, y
Dim as UInteger aBucketPos(0 to 10)
DIm as UInteger p
For x = 0 to Ubound(a) - 1
p = CUbyte((a(x) \ 10 ^ (pa - 1)) Mod 10)
aBucket(aBucketPos(p), p) = a(x) 'hier stürzt es bei großen Bildern ab
aBucketPos(p) += 1
Next
i = 0
For x = 0 to Ubound(aBucketPos)
If aBucketPos(x) > 0 Then
For y = 0 to aBucketPos(x) - 1
a(i) = aBucket(y, x)
i += 1
Next
End If
Next
If pa < 10 Then
RadixSortUInt32(a(), pa + 1)
End If
End Sub
'code by KristopherWindsor -> https://www.freebasic.net/forum/viewtopic.php?f=7&t=10981&hilit=FileOpenDialog
Function FileOpenDialog (Byref sTitle As String, Byref sDir As String = CurDir, sFilter As String = !"All Files (*.*)" + Chr(0) + "*.*" + Chr(0, 0)) As String
Dim oFilename As OPENFILENAME
Dim sFilename As Zstring * (MAX_PATH + 1)
Dim Title As Zstring * 32 => sTitle
Dim sInitialDir As Zstring * 256 => sDir
With oFilename
.lStructSize = SizeOf(OPENFILENAME)
.hwndOwner = NULL
.hInstance = GetModuleHandle(NULL)
'"All Files, (*.*)"
'"*.*"
'"Bas Files, (*.BAS)"
'"*.bas"
'.lpstrFilter = Strptr(!"All Files, (*.*)\0*.*\0Bas Files, (*.BAS)\0*.bas\0\0")
.lpstrFilter = Strptr(sFilter)
.lpstrCustomFilter = NULL
.nMaxCustFilter = 0
.nFilterIndex = 1
.lpstrFile = @sFilename
.nMaxFile = SizeOf(sFilename)
.lpstrFileTitle = NULL
.nMaxFileTitle = 0
.lpstrInitialDir = @sInitialDir
.lpstrTitle = @Title
.Flags = OFN_EXPLORER Or OFN_FILEMUSTEXIST Or OFN_PATHMUSTEXIST
.nFileOffset = 0
.nFileExtension = 0
.lpstrDefExt = NULL
.lCustData = 0
.lpfnHook = NULL
.lpTemplateName = NULL
End With
If (GetOpenFileName(@oFilename) = FALSE) Then Return ""
Return sFilename
End Function
Dim GDIPlusStartupInput As GDIPLUSSTARTUPINPUT
Dim As ULONG_PTR GDIPlusToken
GDIPlusStartupInput.GdiplusVersion = 1
If (GdiplusStartup(@GDIPlusToken, @GDIPlusStartupInput, NULL) <> 0) Then
End 'FAILED TO INIT GDI+!
EndIf
Dim as String sImgFile
sImgFile = FileOpenDialog("Select an image file to load...", "", "Image Files (*.bmp;*.jpg;*.png;*.gif)" + Chr(0) + "*.bmp;*.jpg;*.png;*.gif" + Chr(0))
? "Loading image"
Dim As Integer iStatus
Dim as any Ptr hImage
iStatus = GdipLoadImageFromFile(sImgFile, @hImage)
If iStatus <> 0 Then
GdiplusShutdown(GDIPlusToken)
End
End if
Dim as Double fTimer
fTimer = Timer
If (_GDIPlus_ImageGetPixelFormat(hImage) and PixelFormatAlpha) Then 'check if image has alpha channel
? "Unique color count: " & _GDIPlus_ImageCountColors32(hImage)
Else
? "Unique color count: " & _GDIPlus_ImageCountColors24ASM(hImage)
End If
? "Time: " & (Timer - fTimer) * 1000 & " ms"
GdipDisposeImage(hImage)
GdiplusShutdown(GDIPlusToken)
Sleep
|
Der Code zählt die Farben eines Bildes.
Test Bild (32 Bit): http://www.mediafire.com/file/dlbftkaxloqlhvi/Drops.png
Der Absturz ereignet sich bei mir in Zeile 189 (Sub RadixSortUInt32), wenn pa = 3 ist.
QuickSort ist zwar schneller, aber ich wollte mal Radix Sort testen. 
Danke.
_________________
Gruß
UEZ |
|
| Nach oben |
|
 |
Jojo
alter Rang
Anmeldungsdatum: 12.02.2005
Beiträge: 9736
Wohnort: Neben der Festplatte
|
| Verfasst am: 15.12.2017, 13:28 Titel: |
|
|
Dein Programm alloziert mehrere hundert MB an Speicher; irgendwann geht das schief, und das besonders große Array aBucket kann nicht mehr angelegt werden; beim Schreibzugriff auf dieses Array passiert dann der Crash.
_________________
» Die Mathematik wurde geschaffen, um Probleme zu lösen, die es nicht gäbe, wenn die Mathematik nicht erschaffen worden wäre.
 |
|
| Nach oben |
|
|
UEZ
Anmeldungsdatum: 24.06.2016
Beiträge: 147
Wohnort: Opel Stadt
|
| Verfasst am: 15.12.2017, 14:06 Titel: |
|
|
Hmm, mir ist anscheinend entgangen den Speicherverbrauch zu prüfen.
Aber du hast Recht, der Speicherverbrauch zum Zeitpunkt des Absturzes ist annähernd 1 GB.
Somit ist dieser Code ungeeignet für große Bilder, zumal die Performance auch langsamer als Quick Sort ist.
Anscheinend ist das l in O(n * l) größer als O(n * log n) für Quick Sort.
_________________
Gruß
UEZ |
|
| Nach oben |
|
|
Jojo
alter Rang
Anmeldungsdatum: 12.02.2005
Beiträge: 9736
Wohnort: Neben der Festplatte
|
| Verfasst am: 15.12.2017, 21:20 Titel: |
|
|
Das Problem ist hier insbesondere, dass du zusätzlichen Speicher verwaltest, der dazu auch noch sehr groß ist (10-mal größer als das eigentliche Bild, also bei einem 3000x2000-Bild schon ca. 240MB), während klassische Sortieralgorithmen "in-place" arbeiten, d.h. dort wird nur so viel Speicher verbraucht, wie das Originalbild eh schon belegte. Die von dir genannten O-Terme beziehen sich auf die zeitliche Komplexität, nicht die Speicherkomplexität. Häufig kann man sich Zeit durch Speicher kaufen oder umgekehrt, deswegen könnte Radix-Sort theoretisch schneller sein, aber gleichzeitig auch mehr Speicher verbrauchen.
_________________
» Die Mathematik wurde geschaffen, um Probleme zu lösen, die es nicht gäbe, wenn die Mathematik nicht erschaffen worden wäre.
|
|
| Nach oben |
|
|
UEZ
Anmeldungsdatum: 24.06.2016
Beiträge: 147
Wohnort: Opel Stadt
|
| Verfasst am: 15.12.2017, 22:39 Titel: |
|
|
| Jojo hat Folgendes geschrieben: | | Die von dir genannten O-Terme beziehen sich auf die zeitliche Komplexität, nicht die Speicherkomplexität. |
Richtig, ich meinte auch die Laufzeit und nicht den Speicherverbrauch. Es ging mir primär darum Radix Sort zu testen. Ich werde bei Gelegenheit Insertion Sort implementieren und sehen, wie schnell es für diese spezielle Anwendung ist.
Edit: wie zu erwarten ist Insertion Sort extrem langsam.
Wird eigentlich bei jedem Aufruf der Speicher für das Array aBucket freigegeben?
_________________
Gruß
UEZ |
|
| Nach oben |
|
|
Jojo
alter Rang
Anmeldungsdatum: 12.02.2005
Beiträge: 9736
Wohnort: Neben der Festplatte
|
| Verfasst am: 16.12.2017, 01:18 Titel: |
|
|
Der Speicher wird freigegeben, ja, allerdings kann der Speicher mit der Zeit fragmentieren, was ein Grund dafür sein kann, dass Allozierungen fehlschlagen. Ob das hier passiert kann ich nicht direkt sagen, eigentlich sollte das bei modernen Betriebssystemen kein Problem sein.
_________________
» Die Mathematik wurde geschaffen, um Probleme zu lösen, die es nicht gäbe, wenn die Mathematik nicht erschaffen worden wäre.
|
|
| Nach oben |
|
|
UEZ
Anmeldungsdatum: 24.06.2016
Beiträge: 147
Wohnort: Opel Stadt
|
| Verfasst am: 16.12.2017, 17:15 Titel: |
|
|
Das Speichermanagement scheint nicht gut gelöst zu sein.
Ein Redim
| Code: |
...
If pa < 10 Then
ReDim aBucket(1, 1)
RadixSortUInt32(a(), pa + 1)
End If
...
|
lässt das Programm mit diesem Bild zwar nicht mehr abstürzen, aber bei noch größeren Bildern hilft das leider auch nicht.
_________________
Gruß
UEZ |
|
| Nach oben |
|
|
Sebastian
Administrator
Anmeldungsdatum: 10.09.2004
Beiträge: 5969
Wohnort: Deutschland
|
|
| Nach oben |
|
|
UEZ
Anmeldungsdatum: 24.06.2016
Beiträge: 147
Wohnort: Opel Stadt
|
| Verfasst am: 16.12.2017, 17:54 Titel: |
|
|
| Sebastian hat Folgendes geschrieben: | Hast du mal probiert, ob es Unterschiede gibt, wenn du mit
und (installiertem) gcc compilierst? |
Mit -gen gcc stürzt es auch das große Test Bild (7680 x 4320 Pixel) ab.
_________________
Gruß
UEZ |
|
| Nach oben |
|
|
Jojo
alter Rang
Anmeldungsdatum: 12.02.2005
Beiträge: 9736
Wohnort: Neben der Festplatte
|
| Verfasst am: 17.12.2017, 12:54 Titel: |
|
|
Die Rekursion ist mir gar nicht aufgefallen - aber klar, wenn du ein riesiges Array anlegst und dann in die Rekursion gehst und noch mal so ein riesiges Array anlegst, läuft irgendwann der Speicher über. Also immer auf die Lebenszeiten der Variablen achten, der Compiler wird den belegten Speicher nicht einfach so vor der Rekursion freigeben, weil die Variable bis zum Ende der Funktion lebendig ist.
| Zitat: | | Mit -gen gcc stürzt es auch das große Test Bild (7680 x 4320 Pixel) ab. |
Lass uns mal eben rechnen: 7680 x 4320 Pixel, je vier Byte pro Pixel, zehn Buckets = 7680 x 4320 x 4 x 10 = ~1.3GB an Daten. Da bist du mit dem einen Array schon verdammt nahe am 2GB-Limit, das ein 32-bit-Prozess typischerweise unter Windows hat, außer die Anwendung wurde als "Large Address Aware" markiert. Ob FreeBASIC das bei seinen erzeugten EXEn tut, weiß ich nicht. Natürlich kann auch der tatsächlich vorhandene Arbeitsspeicher schon vorher einen Strich durch die Rechnung machen.
_________________
» Die Mathematik wurde geschaffen, um Probleme zu lösen, die es nicht gäbe, wenn die Mathematik nicht erschaffen worden wäre.
|
|
| Nach oben |
|
|
UEZ
Anmeldungsdatum: 24.06.2016
Beiträge: 147
Wohnort: Opel Stadt
|
| Verfasst am: 17.12.2017, 15:41 Titel: |
|
|
| Jojo hat Folgendes geschrieben: | Die Rekursion ist mir gar nicht aufgefallen - aber klar, wenn du ein riesiges Array anlegst und dann in die Rekursion gehst und noch mal so ein riesiges Array anlegst, läuft irgendwann der Speicher über. Also immer auf die Lebenszeiten der Variablen achten, der Compiler wird den belegten Speicher nicht einfach so vor der Rekursion freigeben, weil die Variable bis zum Ende der Funktion lebendig ist.
| Zitat: | | Mit -gen gcc stürzt es auch das große Test Bild (7680 x 4320 Pixel) ab. |
Lass uns mal eben rechnen: 7680 x 4320 Pixel, je vier Byte pro Pixel, zehn Buckets = 7680 x 4320 x 4 x 10 = ~1.3GB an Daten. Da bist du mit dem einen Array schon verdammt nahe am 2GB-Limit, das ein 32-bit-Prozess typischerweise unter Windows hat, außer die Anwendung wurde als "Large Address Aware" markiert. Ob FreeBASIC das bei seinen erzeugten EXEn tut, weiß ich nicht. Natürlich kann auch der tatsächlich vorhandene Arbeitsspeicher schon vorher einen Strich durch die Rechnung machen. |
Deine Rechnung stimmt zwar, aber der Absturz ereignet sich beim ersten Aufruf von Radix Sort, somit sind nicht ~ 1,3 GB belegt, sondern laut Process Exporer ~450 MB, also ca. 1/10. Ferner sollte doch der Speicher, wie oben erwähnt, mit ReDim aBucket(1, 1) wieder freigegeben werden, bevor die Funktion wieder aufgefrufen wird! D.h. nur 1/10 sprich ca. 450 MB pro Aufruf?
_________________
Gruß
UEZ |
|
| Nach oben |
|
|
Jojo
alter Rang
Anmeldungsdatum: 12.02.2005
Beiträge: 9736
Wohnort: Neben der Festplatte
|
| Verfasst am: 17.12.2017, 16:22 Titel: |
|
|
Dein Array hat bereits beim ersten Aufruf die Dimensionen:
| Code: | | Dim as UInteger aBucket(0 to Ubound(a), 0 to 10) |
Also um genau zu sein sogar 11x, nicht 10x die eigentlich Bildgröße + 1 (also ~1.4GB). Dem Process Explorer (oder auch Task-Manager) ist in dieser Hinsicht nicht immer grenzenlos zu vertrauen, sprich es wird möglicherweise nicht immer den Verbrauch angezeigt, den du dir vorstellst. Da das Array zu Beginn komplett genullt ist, kann beispielsweise das System erkennen, dass der Speicher noch gar nicht zur Verfügung gestellt werden muss - die Adressen dafür sind praktisch schon im Adressraum deines Programms reserviert, aber ein tatsächlich existierender physischer Speicherbereich noch nicht zugewiesen. In diesem Fall wird möglicherweise vom Process Explorer möglicherweise (nicht getestet!) der allozierte, aber noch unbenutzte Speicher gar nicht eingerechnet.
_________________
» Die Mathematik wurde geschaffen, um Probleme zu lösen, die es nicht gäbe, wenn die Mathematik nicht erschaffen worden wäre.
|
|
| Nach oben |
|
|
|
|
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
