My mistake on safeint - I thought there were C & C++ libraries to achieve this; which doesn't make sense in retrospect, you need to throw errors. As for the efficiency, I stated that mine was inefficient, it was for illustration. Most arches will use an add-with-carry instruction to turn a 4-word addition into about 5 instructions, without a loop. You can use assembly, or perhaps better, just skip to the long data type, eliminate the loop, and maybe use a macro instead of a function call.
Unfortunately, you've gotten me way more interested in this than I intended, and I'm certain to be studying kernel code tonight (either linux or minix)... On Tue, Jan 05, 2010 at 09:26:28PM -0800, Bhaktavatsalam Nallanthighal wrote: > Hi, > > I see where you are going with this. Quite interesting that you > sparked two ideas in me. > > Using such methods would make my 128-bit operations a hundred times > slower[first the function call overhead, and the loop etc.] and also I > will not be able to do much with 128-bit datatypes by writing a custom > function for each. However, I could easily implement a 128-bit library > for basic operations, efficiently in assembly language and also > considering endianness using preprocessor options! However, before > doing that, I just want to wait a few more days. This seems to me a > good thing to actually start writing my code. > > Secondly, the thought that _ could be a special variable never came to > me. In C, you could name your variables in anyway with an exception > that it should not start with a number. In fact, all variables in my > operating system's source code start with an _, so that users don't > replicate the names of my variables [considering the fact that very > few people name their variables in that fashion]. I also tend to use a > lot of _'s in my variables. I thought that Minix used an _ just > because giving it a name would not make any sense. But, it could also > be the case that _ is treated specially. I will try investigating into > this a little more deeper. If you can find something interesting with > it, please do let me know about it. > > Coming to the safeint issue, it once again needs me to use C++, > templates and all that stuff, which I want to avoid using. I'm using > pure C, not even the provided libraries[stdio, stdlib, conio etc.] to > build my projects. > > Further, I took a look at Minix's source code and tried tracking the > usage of the datatyped variables. If you could also help me with it, > here is the information: > > The datatype is u64_t [not uint64_t], and is declared on line #72 in / > include/sys/types.h in the Minix source code available at: > http://www.minix3.org/download/minix_source_3_1_1_complete.tar.bz2 > > > Thanks for all your help. > > Bhaktavatsalam Nallanthighal. > [email protected] > > > > > > > On Jan 5, 9:54 am, [email protected] wrote: > > You just need to keep track of overflow -- something like this will > > work (I'm unfamiliar with the _[x] notation used.. is it special?): > > > > uint32_t max(uint32_t a, uint32_t b) { > > if (a >= b) { > > return a; > > } > > return b; > > > > } > > > > uint128_t add128(uint128_t a, uint128_t b) { > > uint128_t retval; > > uint32_t count,overflow = 0; > > for (count = 0; count < 4; count++) { > > retval._[count] = overflow + a._[count] + b._[count]; > > if (retval._[count] < max(a,b)) { > > overflow = 1; > > } else { > > overflow = 0; > > } > > } > > return retval; > > > > } > > > > There's code for a thing called safeint, which I've heard of but never > > used, perhaps you should give that a look. Also, I'm certain there are > > more efficient ways to do what I've done, this is just an example. > > Finally, endianness is very important here - I've assumed little endian, > > but your filesystem might not be. > > > > > > > > On Mon, Jan 04, 2010 at 09:15:24PM -0800, Bhaktavatsalam Nallanthighal > > wrote: > > > Hey back, > > > > > Once again, you exactly nailed my problem. The main reason I'm > > > concerned with this issue is because I'm trying to implement a 128-bit > > > Database Filesystem. The explanation and example you provided were > > > helpful, but please allow me to probe you a little more. Okay, now > > > with the method you described, I have a 128-bit value. > > > > > Staying along the lines of the solution you proposed and if I am not > > > wrong, Prof.Andrew Tanenbaum's Minix Source code has a 64-bit datatype > > > somewhere, that is just a struct containing an array of two uint32's, > > > something like this: > > > > > typedef struct { uint32_t _[2]; } uint64_t; > > > > > In the similar way, I can achieve an 128-bit datatype in C using an > > > array of four 32-bit datatypes [to keep things familiar to me, not 2 > > > 64-bit]. It would be something like this: > > > > > typedef struct { uint32_t _[4]; } uint128_t; > > > > > Suppose I stick to C to keep my filesystem implementation low-level- > > > transparent and clear to me [it is part of a larger project that is > > > being written in C], instead of using C++ [implying that I don't want > > > to overload my operators], and I want to add two 128-bit numbers. Say, > > > in my context, that before unmounting my filesystem, I want to perform > > > a CRC Checksum of my filesystem parameters[just like how a CRC is done > > > with Internet Datagram Headers before pushing them to lower levels] > > > and store it in a Parameter block to mark the partition not-dirty. As > > > my filesystem is 128-bit, I will have to add several 128-bit numbers, > > > how would I accomplish this? > > > > > Thanks once again, for all your time and suggestions. > > > > > Bhaktavatsalam Nallanthighal > > > > > On Jan 4, 5:58 pm, [email protected] wrote: > > > > Unfortunately, you're not talking to a filesystem expert. I know that > > > > actual address space (memory and memory-mapped files) cannot exceed the > > > > addressing capability of the processor i.e. 32 bit systems can only > > > > address > > > > 4GB memory, which causes trouble if you try to mmap a file larger than > > > > 4GB - this is common for database applications. Filesystems, on the > > > > other hand, aren't mapped to memory. You can address a 128 bit memory > > > > location as four 32-bit memory locations. For example, assume the > > > > address is held in dx:ds, and you're loading the data into four 32 bit > > > > registers: > > > > > > mov eax, dx:ds > > > > mov reg1, eax > > > > incf ds > > > > mov eax, dx:ds > > > > . > > > > . > > > > . > > > > mov reg4, eax > > > > > > And now reg1:reg2:reg3:reg4 will have 128 bits of data, 1 memory address > > > > location from the filesystem. I haven't used assembly in awhile, and > > > > the last time I did it was on the PIC, so my syntax above is probably > > > > wrong, but I hope it gets the idea across. In reality, you'd probably > > > > do a table read into contiguous memory from the disk, which would > > > > optimize the operation, but I'd have to look up how to do that :) > > > > > > So, you see, the 32-bit limitation limits only memory address space and > > > > instruction size, but doesn't strictly limit files (unix treats nearly > > > > everything as a file, so disks, and their filesystems, are files.) > > > > > > Anybody know of a good OS development list? Because this question is > > > > getting rather technical, and beyond the scope of a linux users group, > > > > into a developers group. > > > > > > On Mon, Jan 04, 2010 at 02:44:06PM -0800, Bhaktavatsalam Nallanthighal > > > > wrote: > > > > > Hi back, > > > > > > > I appreciate that reply. You really nailed my problem. As you've > > > > > said, I'm confused with instruction size and address space. However, > > > > > I'm more confused about the sizes of the data the instructions operate > > > > > on rather than the instruction size itself [did you mean the way the > > > > > instruction opcodes are CISC packed by "instruction size"?]. Your > > > > > reply in an overall sense was helpful, but was too general for me to > > > > > do anything useful "programmatically". Can you elaborate on how 128- > > > > > bit addresses can be accessed using normal 32-bit instructions > > > > > [assuming that you have that much memory?]? If you can provide a > > > > > simple example, I'd be really really thankful to you. Any pointers > > > > > would also be appreciated. > > > > > > > Bhaktavatsalam Nallanthighal > > > > > > > On Jan 4, 10:19 am, [email protected] wrote: > > > > > > On Mon, Jan 04, 2010 at 01:27:06AM -0800, Bhaktavatsalam > > > > > > Nallanthighal wrote: > > > > > > > Hi, > > > > > > > > > Thanks for the elaborate reply and for the pointer. I've been > > > > > > > reading > > > > > > > various parts of an old Linux kernel, Minix and Unix V 6.0. This > > > > > > > is > > > > > > > along the lines of writing my own kernel. You said that > > > > > > > conditional > > > > > > > compilation is used for various architecture specific features. As > > > > > > > you've suggested, this is evident from the kernel's coding if it > > > > > > > is > > > > > > > supporting a wide range of processors [the preprocessing] But, the > > > > > > > more confusing point to me is how the kernel is able to > > > > > > > consistently > > > > > > > do this across varying architectures. For example, if linux kernel > > > > > > > supports a processor that has no protection features or atleast > > > > > > > not as > > > > > > > many as Intel processors have, how would the overall impact be > > > > > > > managed. > > > > > > > > > For Instance, say that the linux kernel is using the protection > > > > > > > features of the Intel processor to keep user-space programs from > > > > > > > affecting the kernel [which seems to me as the most natural way > > > > > > > to do. > > > > > > > If otherwise, please mention]. If the kernel is able to run on > > > > > > > some > > > > > > > other architecture that does not have these features, does it mean > > > > > > > that it offers no protection? Or does it mean that protection is > > > > > > > implemented in software for that processor. > > > > > > > > > Another Instance, say that the linux kernel supports multitasking > > > > > > > using the hardware features of the Intel processors[TSSes etc. > > > > > > > Please > > > > > > > correct me if this is not the way, again.] How is this able to > > > > > > > port > > > > > > > across some other architecture that does not have these features > > > > > > > in > > > > > > > hardware? Is it implemented in software? > > > > > > > > > Apart from this, I would be helpful if more clarification can be > > > > > > > provided on the issue with supporting higher level datatypes and > > > > > > > different sized-processors. The exact issue is with how linux > > > > > > > supports > > > > > > > higher types during RUNTIME. A best example to represent the > > > > > > > issue, is > > > > > > > with ZFS. I heard somewhere that ZFS[from Sun] is supported on > > > > > > > linux. > > > > > > > But, it is well known that ZFS is a 128-bit file system. If the > > > > > > > processor is able to only manipulate data in 32-bit, how are > > > > > > > 128-bit > > > > > > > operations like addition, subtraction done? Are there any > > > > > > > cascadable- > > > > > > > instructions that provide a carry/borrow/etc. so that each 128-bit > > > > > > > operations require four 32-bit operations? If so, isn't this very > > > > > > > inefficient? > > > > > > > > > You also said that the system calls provide a unified layer to > > > > > > > other > > > > > > > parts of the kernel. Do you mean that each system call is > > > > > > > differently > > > > > > > implemented for each kind of processor? For example, consider > > > > > > > kmalloc > > > > > > > () function. Is kmalloc() implemented differently for each > > > > > > > processor? > > > > > > > > > I'm just few steps away from diving into a linux book. I'm just > > > > > > > trying > > > > > > > to avoid it as much as possible, through asking people due to time > > > > > > > restrictions. Additionally, the website you provided is nice. Good > > > > > > > article on Portable device drivers. > > > > > > > > > Bhaktavatsalam Nallanthighal > > > > > > > > > On Jan 4, 2:11 am, Sid <[email protected]> wrote: > > > > > > > > On Jan 4, 5:34 am, Bhaktavatsalam Nallanthighal > > > > > > > > > > <[email protected]> wrote: > > > > > > > > > Hello, > > > > > > > > > > > Can anyone explain in a clear way, how linux deals with > > > > > > > > > portability across architectures. The main points I'm getting > > > > > > > > > confused > > > > > > > > > are: > > > > > > > > > > > - Does a single linux kernel support processors of varying > > > > > > > > > size? I > > > > > > > > > mean, will the same linux kernel give me the ability to > > > > > > > > > compile it for > > > > > > > > > various sized processors[8-bit, 16-bit, 32-bit, 64-bit]? > > > > > > > > > > Yes, linux kernel supports different processors. Although I am > > > > > > > > not > > > > > > > > sure if it supports an 8 bit one, as linux was first made for > > > > > > > > 80386 > > > > > > > > microprocessor. > > > > > > > > If you configure and compile the kernel yourself, you'll see > > > > > > > > that > > > > > > > > there are options that allow you to compile it for different > > > > > > > > processors. These options are nothing but conditional > > > > > > > > compilation > > > > > > > > statements like #ifdef in the kernel code, so, according to the > > > > > > > > processor you select, the coressponding code for that very > > > > > > > > processor > > > > > > > > is compiled. > > > > > > > > > > > If so, how > > > > > > > > > does it deal with the datatypes consistently? > > > > > > > > > > There is definition for different datatypes and again > > > > > > > > conditional > > > > > > > > compilation is used for the same. If you go through the kernel > > > > > > > > code > > > > > > > > you'll see that there are various directories for different > > > > > > > > architectures. e.g.... > > > > read more » > -- > You received this message because you are subscribed to the Linux Users Group. > To post a message, send email to [email protected] > To unsubscribe, send email to [email protected] > For more options, visit our group at > http://groups.google.com/group/linuxusersgroup
-- You received this message because you are subscribed to the Linux Users Group. To post a message, send email to [email protected] To unsubscribe, send email to [email protected] For more options, visit our group at http://groups.google.com/group/linuxusersgroup
