Navigation

Volume 1, p404 Huffman's method can be generalized to t-ary trees as well as binary trees.

Volume 2, p47 code for 1-5 percent, 95-99 percent.

Volume 2, p7, line 8-9 geiger counter.

We've been having some difficulty toilet training our daughter. To draw her interest, we had to institute a reward system: She gets a piece of chocolate each time she goes in the potty.

She had some success today. Soon after wining a reward for wee-weed in the potty, She sit back to the potty and had a poop. After being cleaned up, she led me to the kitchen, wanted to be picked up, and suggested that I "take a look at the tea." Although the tea is brewing on the counter top, her eyes were focusing on the freezer (where I kept the tea). When I played dumb and did not mention the reward, she finally demanded that she "can eat one."

I'm slowing gaining confidence in programming in MIX assembly language. Yet it still takes some serious mental processing in order to achieve even relatively simple task. However, I feel recording the mental process during problem solving at this stage is actually valuable as it is conscious and may be used to serve the purposes of being a good problem solving process.

We take Exercise 1.3.2-13 of TAoCP as an example.

1. Understand the Problem

The goal is to read a section of code from paper tape and print out a frequency count of the letters in the code. The efficiency requirement of buffering the input, as being a selling point of the program, should be kept in the mind so provisions will be made when ever necessary so as to avoid having to make structural change of the program in the later stage of the project. Aim high, shoot low, that is.

2. Understand the Problem to Find the Angle of Attack

The first draft may be a mixture of code snippets and pseudo-codes:

*
* Provisioning for Input buffers, list of counts
*
BUFFER0 ORIG *+24
EB0     CON  *+1
BUFFER1 ORIG *+24
EB1     CON  *-49
LIST    ORIG *+29

        IOC  0(20)
        initialize to a state as if buffer x just processed
LOOP    preparation before read the next buffer?
        IN    0,?(20)
        do processing of the data in the buffer
        (at the end of processing one buffer, something
        will point to the memory location that points to the
        the next buffer to use.  the initialization at the beginning
        of the program shall simulate that condition)
        JMP  read
* Printing of the result follows ...

Since the printing is not interwoven with the counting, it's implementation is deferred.

3. Attack the Main Issue

From the above analysis, it is clear that the angle of attack should aim at the processing. The initialization part depends on the details to be worked out here.

1H    IN    0,1(20)   [rI1 is still pointing to the next
      INC1  1          until here]
      ENT2  24        start count
      LD3   0,1(1:1)
      LDA   LIST,3    [increment
      INCA  1          the
      STA   LIST,3     count ]
      LD3   0,1(2:2)
      LDA   LIST,3
      INCA  1
      STA   LIST,3
      LD3   0,1(3:3)
      LDA   LIST,3
      INCA  1
      STA   LIST,3
      LD3   0,1(4:4)
      LDA   LIST,3
      INCA  1
      STA   LIST,3
      LD3   0,1(5:5)
      LDA   LIST,3
      INCA  1
      STA   LIST,3
      INC1  1         [next
      DEC2  1          char]
      J2P   2B

It's clear at this point that the initialization required before start reading the buffer is:

      IN    EB1(20)    start input to buffer one, and
      ENT1  EB1        set rI1 to EB1.

Upon starting, the program will kick off the tape reader using buffer1, the second read that uses will be blocked until the buffer1 is filled. In the subsequent iteration, the program will either be blocked at the read, or not, depend on which task, reading or counting the buffered data takes more time.

The printing portion of the problem is relatively simple:

PRINT EQU  18
      ENTA 0
      STRA BUFFER0      [prepare the buffer
      MOV  BUFFER0(24)   for output]
3H    ENT1 30
      STR1 BUFFER0(0:0)
      ENTA 0
      LDX  LIST,1
      JXZ  4F
      CHAR
      STRA BUFFER+1(1:5)
      STRX BUFFER+2(1:5)
      OUT  BUFFER0(PRINT)
4H    DEC1 1
      J1P  3B

Note: the problem does not clearly define the scope for character. For the sake of safety, we may want to reserve 56 word for storing the counts and print only these below Z.

The following is the steps I, as an experienced programmer that's inexperienced in programming in assembling language, had to take to implement solution 1 as described in the book as: "In this solution we run through each row in turn, making a list of all columns in which the row minimum occurs and then checking each column on the list to see if the row minimum is also a column maximum."

1. Planning

Use rI6 to loop through rows. For each row, first use rI5 to loop through columns and find addresses where the minimum is found in that row. Store the addresses in a reserved space and record the number of locations in rI4. After all minimums are located, use rI4 as an index to loop through all minimums to find if the point is the saddle point. Assume the following pseudo-variables are defined before the subroutine is called:

MBASE   EQU 1000         The base address of the matrix
MSIZE   EQU 72            The size of the matrix
MCOLS   EQU 8           The number of columns of the matrix

2. The Program

Now here comes the program:

MINS    ORIG *+COLS          // reserve space for minimum point addresses
RBASE   ORIG *+1             // and for the base address of the current row
SADDLE  STJ  EXIT
        ENT6 MSIZE+COLS
RLOOP   DEC6 COLS
        STR6 RBASE(0:2)      // the base address of the current row
        LD5  RBASE           // TODO check the field
*
* Loop through the current row to find addresses of mins
*
        INC5 COLS
        LDA  MBASE,5
CLOOP   DEC5 1
        CMP5 RBASE
        JLE  RLOOP
* Compare CONTENT(rA) with that in the current location
        CMPA MBASE,5
* Less: do nothing
        JL   CLOOP
        JG   2F
* Equal: strore the address and increment the count (rI4)
        STR5 MINS,4
        INC4 1
* Greater: replace C(rA) and reset the count
2F      LDA  MBASE,5
        ENT4 1
        STR5 MINS
        JMP  CLOOP
*
* Loop through the addresses of located mins to see
* if any of it is a saddle point, note that at least
* one min location will be find
*
CBASE   ORIG *+1
MLOOP   DEC5 RBASE          // got the column number
        STR5 CBASE
        INC5 MSIZE+ROWS
JLOOP   DEC5 ROWS
        CMP5 CBASE
        JLE  FOUND          // all y(i0, j) tested without positive result
        CMPA MBASE,5
        JGE  JLOOP          // not positive, next row
        DEC4 1              // not a saddle point, next candidate
        J4N  RLOOP
        LD5  MIN,4
        JMP  MLOOP
FOUND   LD1  MINS
EXIT    JMP  *

3. Further Improvements

We can use rI1 in the place of rI5, and rI5 in the place of rI4 to save the register usage by one.

mesothelioma is a lung cancer caused by exposure to asbestos.

The solution to 1.3.2-9 of TAoCP presented a tricky way to check for a valid partial field:

FIELD  ENTA 0
       LDX  INST(4:4)
       DIV  =9=
       STX  *+1(0:2)
       INCA 0
       CMPA =5=
       JG   BAD

To understanding the way this code fragment work, two tricks need to be recognized. The first one is that the STX instruction modified the subsequent instruction from "INCA 0" to "INCA r", where r is the reminder of F divided by 9.

The second trick in the code fragment is to verify the partial field by verifying (q+r)≤5, where q and r is the quotient and reminder, respectively, of F divided by 9. The validity of this method can easily to proved.

From:
Sent: Monday, April 10, 2006 2:10 PM
To:
Subject: "cannot access private member declared in class"

From:
Sent: Tuesday, April 11, 2006 8:25 AM
To:
Subject: About type visibility of native type

To me, exercise 1.3.2-9 is definitely a problem of 30+ in difficulty rating. As an inexperienced assemble language programmer, it takes me many hours to come up a solution far inferior than the solution given in the book, not to mention that I even have difficulty understanding the "FIELD" part.

That motivated me to try running the program to see how it works. So I typed the program in and added a few lines to make it a complete program:

INST   CON  VALID
GOOD   OUT  GTEXT(18)
BAD    OUT  BTEXT(18)
GTEXT  ALF  GOOD
BTEXT  ALF  BAD
       END  BEGIN

Incidentally, typing the full program along takes more than ten minutes.

The problem is mixasm, the GNU MDK assembler, doesn't like a mixal "statement" of a mix operation to have an invalid F-field. Thus mixasm complained of "invalid f-specification" in two statements. These are:

TABLE  NOP  GOOD(BMAX)       where BMAX EQU 1(4:4)-1
VALID  CMP  3999,6(6)

Actually, the first one seemed to be a bug with the assembler since MIX spec says the F-field is ignored for NOP. A workaround for the second one is to use CON statement:

VALID  CON  63,3999(0:2),6(3:3),6(4:4)

(Please read on to find the resolution to this issue.)

more...

It's a problem from TAoCP with a difficulty rating of 25. It took me several weeks and many hours to partially finish, with three issues remaining: 1) no support of float point instructions, 2) the address field must be valid in some instructions in which the address field is ignored, and 3) M value of some IO instruction is not verified. The following is my program. Please don't laugh!

GOOD  HLT
BAD   HLT
INST  ORIG *+3000
NUNIT EQU  20
*
* validate the F-field
*
MMAX CON  3999
EIGHT CON  8
FIVE  CON  5
FIELD ENTA 0                SUBROUTINE VERIFY FIELD
      LDX  INST(4:4)        I2 - FIELD (8L+R)
      DIV  EIGHT
      CMPA FIVE
      JG   BAD              L MUST BE NO GREATER THAN 5
      CMPX FIVE
      JG   BAD              R MUST BE NO GREATER THAN 5
QUOT  STA  *
      CMPX QUOT
      JL   BAD
*
* Validate the Address
*
ADDR  LDA  INSTR(0:2)
      LDX  INSTR(3:3)
      CMPA MMAX
      JG   *+2
      JANN *+3
      JXNZ BAD
      JMP  GOOD
      CMPX SIX
      JG   BAD
      JMP  GOOD
*
* varies valid F value
*
FUNIT ENT2 NUNITS
      JMP  2F
FMMAX LD2  MMAX
      JMP  2F
FONE  ENT2 1
      JMP  2F
FTWO  ENT2 2
      JMP  2F
FTHRE ENT2 3
      JMP  2F
FFOUR ENT2 4
      JMP  2F
FFIVE ENT2 5
      JMP  2F
FSIX  ENT2 6
      JMP  2F
FSVN  ENT2 7
      JMP  2F
FEIGH ENT2 8
      JMP  2F
FNINE ENT2 9
      JMP  2F
2H    J2N  BAD
      CMP2 INSTR(4:4)
      JG   BAD
      JMP  ADDR
*
* Main Lookup Table
*
START LD1  INST(5:5)
      LD1  TABLE,1
      JMP  0,1
TABLE CON  GOOD       NOP
      CON  FIELD      SUB
      CON  FIELD      SUB
      CON  FIELD      MUL
      CON  FIELD      DIV
      CON  FTWO       NUM/CHAR/HLT  TODO NO ADDR
      CON  FFIVE      SHIFT
      CON  FMMAX      MOVE
      CON  FIELD      LDA
      CON  FIELD      LD1
      CON  FIELD      LD2
      CON  FIELD      LD3
      CON  FIELD      LD4
      CON  FIELD      LD5
      CON  FIELD      LD6
      CON  FIELD      LDX
      CON  FIELD      LDAN
      CON  FIELD      LD1N
      CON  FIELD      LD2N
      CON  FIELD      LD3N
      CON  FIELD      LD4N
      CON  FIELD      LD5N
      CON  FIELD      LD6N
      CON  FIELD      LDXN
      CON  FIELD      STA
      CON  FIELD      ST1
      CON  FIELD      ST2
      CON  FIELD      ST3
      CON  FIELD      ST4
      CON  FIELD      ST5
      CON  FIELD      ST6
      CON  FIELD      STX
      CON  FIELD      STJ
      CON  FIELD      STZ
      CON  FUNIT      JBUS  TODO OMMIT ADDR
      CON  IOCOP      IOC   TODO
      CON  FUNIT      IN
      CON  FUNIT      OUT
      CON  FUNIT      JRED
      CON  FNINE      JUMP
      CON  FFIVE      JA
      CON  FFIVE      J1
      CON  FFIVE      J2
      CON  FFIVE      J3
      CON  FFIVE      J4
      CON  FFIVE      J5
      CON  FFIVE      J6
      CON  FFIVE      JX
      CON  FTHRE      INCA/DECA/ENTA/ENNA
      CON  FTHRE      R1
      CON  FTHRE      R2
      CON  FTHRE      R2
      CON  FTHRE      R4
      CON  FTHRE      R5
      CON  FTHRE      R6
      CON  FTHRE      RX
      CON  FIELD      CMPA
      CON  FIELD      CMP1
      CON  FIELD      CMP2
      CON  FIELD      CMP3
      CON  FIELD      CMP4
      CON  FIELD      CMP5
      CON  FIELD      CMP6
      CON  FIELD      CMPX

It took longer than I expected but I have a good feeling that most of problem should be resolved by now. Two applications have been built and they run as expected. A chronic of the events in the last phase of the migration is as the following:

At on point, the conclusion seemed to be within reach with Visual Studio 2005. I got so far that I can run the application to completion as long as I supply a set of invalid parameters that takes the application's execution to a route that terminates prematurely with some error code. Still, a portion of the concept is proved. So I collected some test data and fixed the parametered to point to the test data.

The application sufferred a stack overflow as soon as it went into one of the local functions.

Meanwhile, the coop working on building another application was still fighting with more link errors, despite that I let him copied the libraries files of the 3rd party library newly build with VC++8 (a.k.a Visual Studio 2005). Well, I knew I didn't do a through job in putting all the recompiled libraries together into the distribution directory. Besides, I grabbed the latest release of the source code of the third party library.

Could it be that some remaining incompatibility is also the cause of the stack overflow my program is suffering, acting via some long range force? If I help the coop to build the his application, it may shed some light. The result, another chunk of time devoted to build the "right" version of the the library using VC++8.

It turned out that the stack overflow is not related to anything about the third party library. It was cause by a declared local array variable with an oversized size.

The description of another bug with Mircrosoft Moeny 2006 shows yet another bug. Notice that despite that a split was enterred after the "Reinvest Dividend", the split was not applied to the transaction, when both event occurred on the same date.

Notice this bug was discoverred after a reproduction of the earlier bug. All transcation was deleted from the same account and re-enterred during the reproduction of that bug. It's not clear if the bug will occur had the transcations was enterred freshly in an account.

The application displayed the following popup modal dialog window presenting incorrect information to the user:

The bug was discovered in the process of entering the following transcation:

Date	Transaction		Dollar Amount	Share Price	Shares This Transaction	Total Shares
04-12-2005	2004 Partic Cont -ACH		$3,000.00	100.01	29.997	29.997
11-04-2005	Div Reinvest 3.5138		105.40	97.96	1.076	31.073
11-04-2005	Reverse Stock Split		0.00	101.47	-1.076	29.997
11-18-2005	Exchange To Prime MM		3,048.90	101.64	-29.997	0.000

The split on 11-04-2005 was initially entered mistakenly at the rate of 10147 for 9796 before the "Exchange to Prime MM" on 11-18-2005 was enterred as a sale transaction. The mistake in the split ratio led to extra shares remaining in the account.

To correct the error, the erratic split was first removed using the "Update Price" dialog:

Then an attempt to enter a split with the correct conversion ratio was made:

But the application was not able to accept the transaction. Instead, it pops up a dialog as shown earlier.

Background: a) the account was newly created; b) the investment, Target Maturities Trust: 2005 was also new for this Money file.

After a few days of fuddling, all the compiler error and link error are finally gone. The only thing remained is a link warning about use of "uninstantiated typedef of _TEB struct". The first application has been converted to build in Visual Studio 2005, so it seemed to be. Finally, I blow out a big sigh of release.

But wait, here comes the fun of fixing run time errors.

The application is one that uses .NET reflection to execute a member function of a class resides in a dynamically loaded mixed C++ assemble.

The first trouble to deal with was a complain from .NET framework that (un)managed code was been executed during the dll initialization stage. After some searching around, I got past this by tweaking about the project build options, most noteworthyly the removal of the "/NOENTRY" option.

Then the application throw an exception, claiming that the member function it tried to bind to does not exist in the dynamically linked library.

This is an application that not only build under Visual Studio 2003, the executable build under Visual Studio 2003 also runs flawlessly.

So I turned my attention to the link warning about _TEB. After some more searching around the Internet as well as MSDN website, I first decided to set out to complete the task of removing dependency on _vcclrit.h.

That didn't solve the problem. The member function is still not seem by the calling assemble. Not until after losing many more hairs later, I realized that the answer lies in a missing "ref" in the declaration of the class of which the member function been seeked upon resides. This makes the class not garbage collected. The class itself appears in the assemble but without any of the member functions.

Compare to my Hotmail account, my son's Yahoo email account is getting a lot less spam from the likes of wife-and-daughter-killer spammer. Maybe because my son is a minor so Yahoo is more vigilent in not allowing the spam to pass through the filter. Unforturnately, I can still see spams like:

u can bang different [ ] everyday see www.[ ]. com opps i made a space before com

got into my son's inbox.

I placed an order at www.music123.com for some violin related items on Sunday. I'm really disappointed that they're not yet shipped. At least not yet shipped according to the online status.

(Intesting to see that as soon as this entry is posted, music123's ad is displayed at the top of the list. It went away after a few refreshes.)

Here's a bug in Textpattern, a Blogware as good as Nucleus CMS if not better:

bracket should be avoid in alternative text for images. It will cause the translation of textile to html to fail.