Logic behind the implementation of the "non-native" data type

Question

0.00/5 (No votes)

See more:

Suppose that the hardware of a computer contains an instruction :-

C++

MOVE (source, dest, length) // Hardware instructions are presented using UPPERCASE letters

that copies a character string of length bytes from an address specified by source to an address specified by dest.

The length must be specified by an integer.

An example of this instruction is MOVE (a,b,3) which copies the three bytes starting at location a to the three bytes starting at location b.

NOTE : To refer to a location that is 4 bytes beyond a, the notation a[4] will be used to refer to this location.

Also, to refer to the address given by adding the binary integer constants of the byte at x to the address a, the notation a[x] is used.

The MOVE operation requires a programmer to specify the length of the string to be copied. Thus its operand is a fixed character length string(the lenght of the string must be known).

Here, a fixed length string and a byte-sized binary integer may be considered as "native" data type for this "particular machine".

Problem :
Now, suppose we wished to implement varying-length character strings on this particular machine. That is, we want to enable programmers to use an instruction

C++

MOVEVAR (source,dest)

to move a character string from location source to location dest without being required to specify any length.

Solution :

To implement this data type, we must first decide how it is to be represented in the memory of the machine and then indicate how that representation is to be manipulated. Clearly, it is necessary to know how many bytes must be moved to execute this instruction. Since the MOVEVAR operation doesn't specify this number, therefore the number must be contained within the representation of the character string itself. A varying-length character string of length l may be represented by contiguous set of l+1 bytes (l<256). The first byte contains the binary representation and the remaining bytes contain the representations of the characters in the string.

The program to implement the MOVEVAR operation can be written as follows :-

C++

MOVE (source,dest,1);
for (i=1; i<dest; i++)
{
    MOVE(source[i], dest[i], 1);
}

Source of the problem : Refer page 20
(Screenshot of the page)

My Question :-

Can someone please explain the logic of this implementation of MOVEVAR instruction i.e., the algorithm of the implementation (How it works ?)

What I have tried:

I tried to look up for the explanation but couldn't find it.

Posted 1-Nov-16 8:24am

Shubham_Dubey

Updated 3-Nov-16 6:23am

v3

Add a Solution

2 solutions

Solution 1

Most instruction sets implement this using registers that automatically increment after each byte is copied. The number to copy is put in a special register that counts down for each repetition of the copy. See Intel Instruction Set - REP[^].

Posted 1-Nov-16 8:40am

Richard MacCutchan

Comments

Shubham_Dubey 3-Nov-16 9:16am

Can you explain the algorithm in layman's terms ?
I mean to say that can you please explain it without the terms like registers or counters.
For example, what the for loop in MOVEVAR does and why the loop count variable starts from 1 and goes to (dest-1) ?

Richard MacCutchan 3-Nov-16 9:24am

The code you have does not make sense:


for (i=1; i<dest; i++)

dest is a location, you need to compare i to the number of bytes to copy.

You would be better studying a book or some tutorials. It is impossible to learn programming just by posting questions here.

Shubham_Dubey 3-Nov-16 9:43am

Well, this code also doesn't make much sense to me too, that's why I put a link to the source of the question.
You can check the link because i am pretty sure that you didn't.
And, also i am not trying to just post questions here and not work them out myself.
I tried to understand the implementation, but couldn't understand it.
I am studying from "Data Structures using C" by Aaron M. Tenenbaum and this is a well respected and a top level book on data structures.
So, better read the question carefully and the link provided, or you are always free to leave this question and get away if you can't answer it.

Richard MacCutchan 3-Nov-16 10:45am

Yes I did read the link; it points to a book for sale, so not much use. But ignoring that, if you cannot provide all the details of your problem in the question then it is difficult for us to help you.

And please remember that everyone here is giving their time at no cost to you, so maybe you should be a bit more polite with your comments.

Shubham_Dubey 3-Nov-16 11:08am

With all due respect the link provided points to Google books showing some of the starting pages of the book "Data Structures using C" by Aaron M. Tenenbaum and it do shows page 20 which contains the stated code.
Also, I didn't mean to be impolite, I am just irritated because I haven't got the explanation i was hoping for.
Sorry, if I offended you earlier.

Richard MacCutchan 3-Nov-16 11:30am

Sorry, but all I get at that link is the front cover of the book, no content. However, my previous comment stands: if you want help with your problem then you need to provide all the details here in your question.

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Richard MacCutchan · Accepted Answer · 2016-11-03T05:44:00

Assuming that the first byte of the source data contains the string length we could have something like:

--------------------------
|  4 |  A |  B |  C |  D |
--------------------------

So the MOVE loop would be:

C++

// move the length byte from the source to the destination
MOVE (source,dest,1);  // dest[0] now contains 4
for (i=1; i <dest; i++)="" set="" i="1," and="" while="" <="" 4="" do="" the="" following<!--="" newline="" --="">{
    MOVE(source[i], dest[i], 1); // move the source byte at offset i to 
                                 // the byte at offset i of the destination
} // increment i and repeat while the value of i is less than 4

This will fail since the loop will terminate before copying the byte at offset 4 thus:

Value of i   copy byte
    1           A
    2           B
    3           C
    4 -> loop terminates since i is not less than byte 0 of dest.

so the for loop needs to be

C++

for (i=1; i <= dest; i++)