Index
> Main > I hate to ask, but HELP! |
| Author |
|
|
Patrick_ 15 Aug 2008, 19:24
I'm rewriting the NeuQuant image quantizing algorithm in assembly. I use it to process GIF's in one of my programs, but I was hoping to get some better performance out of it, therefore I'm rewriting it in assembly.
Anyway, I've looked over every instruction about 5 times but still can't find the issue. To me the code exactly matches up to the C code, so I'm thinking I'm doing something in assembly the wrong way. I know, some of the code isn't the best; currently it's not highly optimized, as I'm just trying to get it to work. As you can see it uses the C calling convention because these functions are called from a C program. If anyone can find the problem, I'd *really* appreciate it.  Here's the code:
neuquant.inc: Code: ;; neuquant.inc: Include file for neuquant.asm. NET_SIZE = 256 ;number of colors used ;; For 256 colours, fixed arrays need 8kb, plus space for the image ;; four primes near 500 - assume no image has a length so large */ ;; that it is divisible by all four primes */ PRIME_1 = 499 PRIME_2 = 491 PRIME_3 = 487 PRIME_4 = 503 MIN_PICTURE_BYTES = (3*PRIME_4) ;minimum size for input image MAX_NET_POS = (NET_SIZE-1) NET_BIAS_SHIFT = 4 ;bias for color values N_CYCLES = 100 ;number of learning cycles ;; Definitions for freq and bias INT_BIAS_SHIFT = 16 ;bias for fractions INT_BIAS = (1 shl INT_BIAS_SHIFT) GAMMA_SHIFT = 10 ;gamma = 1024 GAMMA = (1 shl GAMMA_SHIFT) BETA_SHIFT = 10 BETA = (INT_BIAS shr BETA_SHIFT) ;beta == 1/1024 BETA_GAMMA = (INT_BIAS shl (GAMMA_SHIFT - BETA_SHIFT)) ;; Definitions for decreasing radius factor INIT_RAD = (NET_SIZE shr 3) ;for 256 cols, radius starts RADIUS_BIAS_SHIFT = 6 ;at 32.0 biased by 6 bits RADIUS_BIAS = (1 shl RADIUS_BIAS_SHIFT) INIT_RADIUS = (INIT_RAD * RADIUS_BIAS) ;and decreases by a RADIUS_DEC = 30 ;factor of 1/30 each cycle ;; Definitions for decreasing alpha factor ALPHA_BIAS_SHIFT = 10 ;alpha strats at 1.0 INIT_ALPHA = (1 shl ALPHA_BIAS_SHIFT) ;; RAD_BIAS and ALPHA_RAD_BIAS used for radpower calculation RAD_BIAS_SHIFT = 8 RAD_BIAS = (1 shl RAD_BIAS_SHIFT) ALPHA_RAD_B_SHIFT = (ALPHA_BIAS_SHIFT + RAD_BIAS_SHIFT) ALPHA_RAD_BIAS = (1 shl ALPHA_RAD_B_SHIFT) BEST_D_CONTEST = not (1 shr 31) macro ccall proc,[arg] ; directly call CDECL procedure { common size@ccall = 0 if ~ arg eq reverse pushd arg size@ccall = size@ccall+4 common end if call proc if size@ccall add esp,size@ccall end if } ;; pushad, but no eax macro pushad_noeax { push ecx edx ebx sub esp, 4 mov [esp], esp push ebp esi edi } ;; popad, but no eax macro popad_noeax { pop edi esi ebp add esp, 4 pop ebx edx ecx } PNOEAX_OFFSET = 28 PUSHAD_OFFSET = 32 neuquant.asm: Code: ;; NeuQuant Neural-Net Quantization Algorithm ;; x86 assembly rewrite based on NEUQUANT.C: ;; ------------------------------------------ ;; ;; Copyright (c) 1994 Anthony Dekker ;; ;; NEUQUANT Neural-Net quantization algorithm by Anthony Dekker, 1994. ;; See "Kohonen neural networks for optimal colour quantization" ;; in "Network: Computation in Neural Systems" Vol. 5 (1994) pp 351-367. ;; for a discussion of the algorithm. ;; See also http://members.ozemail.com.au/~dekker/NEUQUANT.HTML ;; ;; Any party obtaining a copy of these files from the author, directly or ;; indirectly, is granted, free of charge, a full and unrestricted irrevocable, ;; world-wide, paid up, royalty-free, nonexclusive right and license to deal ;; in this software and documentation files (the "Software"), including without ;; limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, ;; and/or sell copies of the Software, and to permit persons who receive ;; copies from any such party to do so, with the only requirement being ;; that this copyright notice remain intact. ;; ;; ------------------------------------------ ;; x86 assembly rewrite: ;; ;; Copyright (c) 2008 ;; ;; Permission to use, copy, modify, and/or distribute this software for any ;; purpose with or without fee is hereby granted, provided that the above ;; copyright notice and this permission notice appear in all copies. ;; ;; THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES ;; WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF ;; MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ;; ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES ;; WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ;; ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF ;; OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. format MS COFF public neuquant_initnet as '_neuquant_initnet' public neuquant_unbiasnet as '_neuquant_unbiasnet' public neuquant_writecolourmap as '_neuquant_writecolourmap' public neuquant_inxbuild as '_neuquant_inxbuild' public neuquant_inxsearch as '_neuquant_inxsearch' public neuquant_learn as '_neuquant_learn' include 'neuquant.inc' ;; @neuquant_initnet(unsigned char *the_pic, int len, int sample): ;; ;; Initialise network in range (0,0,0) to (255,255,255) and set parameters ;; Returns nothing. ARG_THE_PIC = PUSHAD_OFFSET+4 ARG_LEN = PUSHAD_OFFSET+8 ARG_SAMPLE = PUSHAD_OFFSET+12 neuquant_initnet: pushad mov ebp, esp mov eax, dword [ebp+ARG_THE_PIC] ;thepicture = thepic; mov dword [the_picture], eax mov eax, dword [ebp+ARG_LEN] ;lengthcount = len; mov dword [length_count], eax mov eax, dword [ebp+ARG_SAMPLE] ;samplefac = sample; mov dword [sample_fac], eax ;; for (i=0; i<netsize; i++) { xor ecx, ecx .for_begin: cmp ecx, NET_SIZE jnl .for_end imul edi, ecx, network_WIDTH*4 ;p = network[i]; add edi, dword network ;; p[0] = p[1] = p[2] = (i << (netbiasshift+ Last edited by Patrick_ on 02 Nov 2010, 20:03; edited 1 time in total |
|||
15 Aug 2008, 19:24 |
|
)/netsize;
|
tom tobias 15 Aug 2008, 22:07
Thank you for this opportunity to preach my message of PROGRAM versus CODE.
revolution wrote: Whoa, that is a lot of code to go over for one posting. Question: would it still be so arduous to investigate, if it were properly written as a PROGRAM? Let's took a look at some of the code, to illustrate what it is about this snippet of code that makes it so difficult: (A program, to cut the lecture short, is READABLE, like a book. Code, on the other hand, must be deciphered, and therefore cannot be readily and quickly debugged. Ah, boy I like those heights. Umm, very nice being up there so high on my soapbox...) Patrick McCann, in neuquant.asm, after eleven lines of text, warning thieves about legal consequences of appropriating this buggy software, wrote: ;; @neuquant_altersingle(int alpha, int i, int b, int g, int r): (A program = Algorithm plus data structures:) Notice three points: 1. I have no idea, looking at this code, what the program is attempting to accomplish. I cannot deduce the algorithm. How can I find a mistake, perhaps very subtle, if I cannot READ what the program is supposed to be accomplishing. Earlier in the code, you have those infernal @@ signs, instead of human readable labels. This is typical of coders, not programmers. You write about, (or perhaps the first author wrote about) Neurons, as if you somehow imagine that these biological structures have something to do with your code. They do not. Use of the word NEURON, conveys absolutely NOTHING to anyone remotely familiar with cpu architecture. "Neural Networks" is a MARKETING PLOY, not a computer programming method. Above all, do NOT imagine that you are somehow explaining to us, or to anyone else, how this obscure code functions, by including the word NEURON, in the "documentation" of this code. 2. Your documentation is not only SPARSE, it is essentially non-existant. Where you do make an effort to "explain" some lines of code, you employ a semicolon on a line with some obscure C code, i.e. code to explain code. Very nice. You have sufficient contempt for the documentation process that you allow your C code comments to spill over onto the next line, so that it is IMPOSSIBLE to comprehend, at a glance. One gets vertigo trying to read the few comments provided. You need to employ WHOLE, entire lines of text, to explain what is going on in each instruction, in lieu of : ";*n -= (alpha*(*n - b)) / initalpha; What, you mean to define a pointer to n by subtracting alpha multiplied by n - b, divided by initalpha??? What's that? Am I supposed to understand that? Your variable names are counterintuitive. Initalpha??? What does that mean? n? b? alpha? 3. You have two modules, one is .inc, one is .asm. Why? Why two modules, not 20? Why two and not ONE? There is NO OVERVIEW. No one can possibly analyze this code, efficiently, absent a proper explanation of what exactly you are trying to accomplish, and why? That is the purpose of the overview, which will also explain the decision to assemble two separate files. There must be a valid reason to break the code up into two different files? What is it? Have you tried SIMPLIFIYING this spaghetti code, and adding some print statements, to ensure that you understand the flow of the program, then gradually reintroducing successively the parts deleted? |
|||
|
15 Aug 2008, 22:07 |
|
|
Patrick_ 15 Aug 2008, 22:59
Thanks for being so kind, tom! I'm sure you've also told Tomasz Grysztar this, as well, what with the commentless-code that makes flat assembler. (I'm not complaining, FASM is great
)
Also, I usually comment my code; however, since this is completely based off of NEUQUANT.C, I simply comment the code with the respective C code that it's written from. If you follow the assembly code along with the C code, it's easy to tell what's going on, even though I myself don't understand how the NeuQuant algorithm works (it's above my head). But you're not required to know much of how it works, as long as you have the source. I know that sounds funny but in this case it's true. Now that I think of it, it probably is too much to ask, you folks analyzing all that source code. It's just that from the source I've seen of the MenuetOS kernel and applications, and FASM, and the lack of complaint as to the extremely sparse comments, I figured you guys would be able to handle it. I'll keep trying myself. Thanks again, tom; I think I've made a new friend today.  |
|||
|
15 Aug 2008, 22:59 |
|
|
tom tobias 16 Aug 2008, 02:37
Patrick wrote: I'm sure you've also told Tomasz Grysztar this, as well,... As a matter of fact, Yes. Many times, for several years. Generally in the form of private messages, however. Patrick wrote: I myself don't understand how the NeuQuant algorithm works (it's above my head). If you don't understand it, then, it is a reflection, not of you, or your supposed "limitations", but of the ideology itself, which is phony as a three dollar bill. 2. No one. NO ONE can properly write a program in any language, but especially not assembly language, without having a properly constructed algorithm. Code, yes. People can slop together a bunch of instructions, which appear to "work", i.e. function appropriately, UNTIL that point in time, when someone seeks to CHANGE something, as you are attempting to do, now. Cheers! |
|||
|
16 Aug 2008, 02:37 |
|
|
bitRAKE 16 Aug 2008, 03:21
I found your conversion to be fairly consistent and your use of syntax not too difficult to grasp. Here is what I believe to be the first error:
Code: cmp ecx, eax ;if (i != smallpos) jne @f Do you use a debugger? Stepping through the code should help. |
|||
|
16 Aug 2008, 03:21 |
|
|
Madis731 16 Aug 2008, 20:44
To my personal dislike:
Code:
format MS COFF
Why can't I just take it to FASM and hit F9 
Code: ;what about wrapping it to simple executable: format PE... |
|||
|
16 Aug 2008, 20:44 |
|
|
Madis731 16 Aug 2008, 20:49
EDIT: OOps, double-post
Last edited by Madis731 on 17 Aug 2008, 11:52; edited 1 time in total |
|||
|
16 Aug 2008, 20:49 |
|
|
Patrick_ 16 Aug 2008, 21:31
tom: Thanks, that was a bit more bearable. My thing with NeuQuant is that the source was available and I was therefore able to use it in my program without rewriting it. Also, it works fairly well.
bitR: Sheesh, thanks! That certainly did make a difference. It's *almost* fixed, but I should be able to take it from here. And yes, I'm using olly as my debugger. Madis: I'm compiling it into an object file so I can link it against my C program. |
|||
|
16 Aug 2008, 21:31 |
|
|
Madis731 17 Aug 2008, 12:00
@Patrick_: So there's no way we can test it as a real application :S
|
|||
|
17 Aug 2008, 12:00 |
|
< Last Thread | Next Thread > |
Forum Rules:
|