diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | COPYING | 674 | ||||
| -rw-r--r-- | HACKING | 83 | ||||
| -rw-r--r-- | Makefile | 6 | ||||
| -rw-r--r-- | README | 101 | ||||
| -rw-r--r-- | asm.sh | 1133 | ||||
| -rw-r--r-- | eval.asm | 258 | ||||
| -rw-r--r-- | examples/cat.sysf | 19 | ||||
| -rw-r--r-- | examples/hello.sysf | 54 | ||||
| -rw-r--r-- | examples/primes.sysf | 129 | ||||
| -rw-r--r-- | examples/primes2.sysf | 195 | ||||
| -rwxr-xr-x | main.sh | 62 | ||||
| -rw-r--r-- | parse.asm | 996 | ||||
| -rw-r--r-- | start.asm | 456 | ||||
| -rw-r--r-- | string.asm | 40 | ||||
| -rw-r--r-- | type.asm | 555 |
16 files changed, 4762 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..588127b --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +/sysf @@ -0,0 +1,674 @@ + GNU GENERAL PUBLIC LICENSE + Version 3, 29 June 2007 + + Copyright (C) 2007 Free Software Foundation, Inc. <https://fsf.org/> + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + + Preamble + + The GNU General Public License is a free, copyleft license for +software and other kinds of works. + + The licenses for most software and other practical works are designed +to take away your freedom to share and change the works. By contrast, +the GNU General Public License is intended to guarantee your freedom to +share and change all versions of a program--to make sure it remains free +software for all its users. We, the Free Software Foundation, use the +GNU General Public License for most of our software; it applies also to +any other work released this way by its authors. You can apply it to +your programs, too. + + When we speak of free software, we are referring to freedom, not +price. Our General Public Licenses are designed to make sure that you +have the freedom to distribute copies of free software (and charge for +them if you wish), that you receive source code or can get it if you +want it, that you can change the software or use pieces of it in new +free programs, and that you know you can do these things. + + To protect your rights, we need to prevent others from denying you +these rights or asking you to surrender the rights. Therefore, you have +certain responsibilities if you distribute copies of the software, or if +you modify it: responsibilities to respect the freedom of others. + + For example, if you distribute copies of such a program, whether +gratis or for a fee, you must pass on to the recipients the same +freedoms that you received. You must make sure that they, too, receive +or can get the source code. And you must show them these terms so they +know their rights. + + Developers that use the GNU GPL protect your rights with two steps: +(1) assert copyright on the software, and (2) offer you this License +giving you legal permission to copy, distribute and/or modify it. + + For the developers' and authors' protection, the GPL clearly explains +that there is no warranty for this free software. For both users' and +authors' sake, the GPL requires that modified versions be marked as +changed, so that their problems will not be attributed erroneously to +authors of previous versions. + + Some devices are designed to deny users access to install or run +modified versions of the software inside them, although the manufacturer +can do so. This is fundamentally incompatible with the aim of +protecting users' freedom to change the software. The systematic +pattern of such abuse occurs in the area of products for individuals to +use, which is precisely where it is most unacceptable. Therefore, we +have designed this version of the GPL to prohibit the practice for those +products. If such problems arise substantially in other domains, we +stand ready to extend this provision to those domains in future versions +of the GPL, as needed to protect the freedom of users. + + Finally, every program is threatened constantly by software patents. +States should not allow patents to restrict development and use of +software on general-purpose computers, but in those that do, we wish to +avoid the special danger that patents applied to a free program could +make it effectively proprietary. To prevent this, the GPL assures that +patents cannot be used to render the program non-free. + + The precise terms and conditions for copying, distribution and +modification follow. + + TERMS AND CONDITIONS + + 0. Definitions. + + "This License" refers to version 3 of the GNU General Public License. + + "Copyright" also means copyright-like laws that apply to other kinds of +works, such as semiconductor masks. + + "The Program" refers to any copyrightable work licensed under this +License. Each licensee is addressed as "you". "Licensees" and +"recipients" may be individuals or organizations. + + To "modify" a work means to copy from or adapt all or part of the work +in a fashion requiring copyright permission, other than the making of an +exact copy. The resulting work is called a "modified version" of the +earlier work or a work "based on" the earlier work. + + A "covered work" means either the unmodified Program or a work based +on the Program. + + To "propagate" a work means to do anything with it that, without +permission, would make you directly or secondarily liable for +infringement under applicable copyright law, except executing it on a +computer or modifying a private copy. Propagation includes copying, +distribution (with or without modification), making available to the +public, and in some countries other activities as well. + + To "convey" a work means any kind of propagation that enables other +parties to make or receive copies. Mere interaction with a user through +a computer network, with no transfer of a copy, is not conveying. + + An interactive user interface displays "Appropriate Legal Notices" +to the extent that it includes a convenient and prominently visible +feature that (1) displays an appropriate copyright notice, and (2) +tells the user that there is no warranty for the work (except to the +extent that warranties are provided), that licensees may convey the +work under this License, and how to view a copy of this License. If +the interface presents a list of user commands or options, such as a +menu, a prominent item in the list meets this criterion. + + 1. Source Code. + + The "source code" for a work means the preferred form of the work +for making modifications to it. "Object code" means any non-source +form of a work. + + A "Standard Interface" means an interface that either is an official +standard defined by a recognized standards body, or, in the case of +interfaces specified for a particular programming language, one that +is widely used among developers working in that language. + + The "System Libraries" of an executable work include anything, other +than the work as a whole, that (a) is included in the normal form of +packaging a Major Component, but which is not part of that Major +Component, and (b) serves only to enable use of the work with that +Major Component, or to implement a Standard Interface for which an +implementation is available to the public in source code form. A +"Major Component", in this context, means a major essential component +(kernel, window system, and so on) of the specific operating system +(if any) on which the executable work runs, or a compiler used to +produce the work, or an object code interpreter used to run it. + + The "Corresponding Source" for a work in object code form means all +the source code needed to generate, install, and (for an executable +work) run the object code and to modify the work, including scripts to +control those activities. However, it does not include the work's +System Libraries, or general-purpose tools or generally available free +programs which are used unmodified in performing those activities but +which are not part of the work. For example, Corresponding Source +includes interface definition files associated with source files for +the work, and the source code for shared libraries and dynamically +linked subprograms that the work is specifically designed to require, +such as by intimate data communication or control flow between those +subprograms and other parts of the work. + + The Corresponding Source need not include anything that users +can regenerate automatically from other parts of the Corresponding +Source. + + The Corresponding Source for a work in source code form is that +same work. + + 2. Basic Permissions. + + All rights granted under this License are granted for the term of +copyright on the Program, and are irrevocable provided the stated +conditions are met. This License explicitly affirms your unlimited +permission to run the unmodified Program. The output from running a +covered work is covered by this License only if the output, given its +content, constitutes a covered work. This License acknowledges your +rights of fair use or other equivalent, as provided by copyright law. + + You may make, run and propagate covered works that you do not +convey, without conditions so long as your license otherwise remains +in force. You may convey covered works to others for the sole purpose +of having them make modifications exclusively for you, or provide you +with facilities for running those works, provided that you comply with +the terms of this License in conveying all material for which you do +not control copyright. Those thus making or running the covered works +for you must do so exclusively on your behalf, under your direction +and control, on terms that prohibit them from making any copies of +your copyrighted material outside their relationship with you. + + Conveying under any other circumstances is permitted solely under +the conditions stated below. Sublicensing is not allowed; section 10 +makes it unnecessary. + + 3. Protecting Users' Legal Rights From Anti-Circumvention Law. + + No covered work shall be deemed part of an effective technological +measure under any applicable law fulfilling obligations under article +11 of the WIPO copyright treaty adopted on 20 December 1996, or +similar laws prohibiting or restricting circumvention of such +measures. + + When you convey a covered work, you waive any legal power to forbid +circumvention of technological measures to the extent such circumvention +is effected by exercising rights under this License with respect to +the covered work, and you disclaim any intention to limit operation or +modification of the work as a means of enforcing, against the work's +users, your or third parties' legal rights to forbid circumvention of +technological measures. + + 4. Conveying Verbatim Copies. + + You may convey verbatim copies of the Program's source code as you +receive it, in any medium, provided that you conspicuously and +appropriately publish on each copy an appropriate copyright notice; +keep intact all notices stating that this License and any +non-permissive terms added in accord with section 7 apply to the code; +keep intact all notices of the absence of any warranty; and give all +recipients a copy of this License along with the Program. + + You may charge any price or no price for each copy that you convey, +and you may offer support or warranty protection for a fee. + + 5. Conveying Modified Source Versions. + + You may convey a work based on the Program, or the modifications to +produce it from the Program, in the form of source code under the +terms of section 4, provided that you also meet all of these conditions: + + a) The work must carry prominent notices stating that you modified + it, and giving a relevant date. + + b) The work must carry prominent notices stating that it is + released under this License and any conditions added under section + 7. This requirement modifies the requirement in section 4 to + "keep intact all notices". + + c) You must license the entire work, as a whole, under this + License to anyone who comes into possession of a copy. This + License will therefore apply, along with any applicable section 7 + additional terms, to the whole of the work, and all its parts, + regardless of how they are packaged. This License gives no + permission to license the work in any other way, but it does not + invalidate such permission if you have separately received it. + + d) If the work has interactive user interfaces, each must display + Appropriate Legal Notices; however, if the Program has interactive + interfaces that do not display Appropriate Legal Notices, your + work need not make them do so. + + A compilation of a covered work with other separate and independent +works, which are not by their nature extensions of the covered work, +and which are not combined with it such as to form a larger program, +in or on a volume of a storage or distribution medium, is called an +"aggregate" if the compilation and its resulting copyright are not +used to limit the access or legal rights of the compilation's users +beyond what the individual works permit. Inclusion of a covered work +in an aggregate does not cause this License to apply to the other +parts of the aggregate. + + 6. Conveying Non-Source Forms. + + You may convey a covered work in object code form under the terms +of sections 4 and 5, provided that you also convey the +machine-readable Corresponding Source under the terms of this License, +in one of these ways: + + a) Convey the object code in, or embodied in, a physical product + (including a physical distribution medium), accompanied by the + Corresponding Source fixed on a durable physical medium + customarily used for software interchange. + + b) Convey the object code in, or embodied in, a physical product + (including a physical distribution medium), accompanied by a + written offer, valid for at least three years and valid for as + long as you offer spare parts or customer support for that product + model, to give anyone who possesses the object code either (1) a + copy of the Corresponding Source for all the software in the + product that is covered by this License, on a durable physical + medium customarily used for software interchange, for a price no + more than your reasonable cost of physically performing this + conveying of source, or (2) access to copy the + Corresponding Source from a network server at no charge. + + c) Convey individual copies of the object code with a copy of the + written offer to provide the Corresponding Source. This + alternative is allowed only occasionally and noncommercially, and + only if you received the object code with such an offer, in accord + with subsection 6b. + + d) Convey the object code by offering access from a designated + place (gratis or for a charge), and offer equivalent access to the + Corresponding Source in the same way through the same place at no + further charge. You need not require recipients to copy the + Corresponding Source along with the object code. If the place to + copy the object code is a network server, the Corresponding Source + may be on a different server (operated by you or a third party) + that supports equivalent copying facilities, provided you maintain + clear directions next to the object code saying where to find the + Corresponding Source. Regardless of what server hosts the + Corresponding Source, you remain obligated to ensure that it is + available for as long as needed to satisfy these requirements. + + e) Convey the object code using peer-to-peer transmission, provided + you inform other peers where the object code and Corresponding + Source of the work are being offered to the general public at no + charge under subsection 6d. + + A separable portion of the object code, whose source code is excluded +from the Corresponding Source as a System Library, need not be +included in conveying the object code work. + + A "User Product" is either (1) a "consumer product", which means any +tangible personal property which is normally used for personal, family, +or household purposes, or (2) anything designed or sold for incorporation +into a dwelling. In determining whether a product is a consumer product, +doubtful cases shall be resolved in favor of coverage. For a particular +product received by a particular user, "normally used" refers to a +typical or common use of that class of product, regardless of the status +of the particular user or of the way in which the particular user +actually uses, or expects or is expected to use, the product. A product +is a consumer product regardless of whether the product has substantial +commercial, industrial or non-consumer uses, unless such uses represent +the only significant mode of use of the product. + + "Installation Information" for a User Product means any methods, +procedures, authorization keys, or other information required to install +and execute modified versions of a covered work in that User Product from +a modified version of its Corresponding Source. The information must +suffice to ensure that the continued functioning of the modified object +code is in no case prevented or interfered with solely because +modification has been made. + + If you convey an object code work under this section in, or with, or +specifically for use in, a User Product, and the conveying occurs as +part of a transaction in which the right of possession and use of the +User Product is transferred to the recipient in perpetuity or for a +fixed term (regardless of how the transaction is characterized), the +Corresponding Source conveyed under this section must be accompanied +by the Installation Information. But this requirement does not apply +if neither you nor any third party retains the ability to install +modified object code on the User Product (for example, the work has +been installed in ROM). + + The requirement to provide Installation Information does not include a +requirement to continue to provide support service, warranty, or updates +for a work that has been modified or installed by the recipient, or for +the User Product in which it has been modified or installed. Access to a +network may be denied when the modification itself materially and +adversely affects the operation of the network or violates the rules and +protocols for communication across the network. + + Corresponding Source conveyed, and Installation Information provided, +in accord with this section must be in a format that is publicly +documented (and with an implementation available to the public in +source code form), and must require no special password or key for +unpacking, reading or copying. + + 7. Additional Terms. + + "Additional permissions" are terms that supplement the terms of this +License by making exceptions from one or more of its conditions. +Additional permissions that are applicable to the entire Program shall +be treated as though they were included in this License, to the extent +that they are valid under applicable law. If additional permissions +apply only to part of the Program, that part may be used separately +under those permissions, but the entire Program remains governed by +this License without regard to the additional permissions. + + When you convey a copy of a covered work, you may at your option +remove any additional permissions from that copy, or from any part of +it. (Additional permissions may be written to require their own +removal in certain cases when you modify the work.) You may place +additional permissions on material, added by you to a covered work, +for which you have or can give appropriate copyright permission. + + Notwithstanding any other provision of this License, for material you +add to a covered work, you may (if authorized by the copyright holders of +that material) supplement the terms of this License with terms: + + a) Disclaiming warranty or limiting liability differently from the + terms of sections 15 and 16 of this License; or + + b) Requiring preservation of specified reasonable legal notices or + author attributions in that material or in the Appropriate Legal + Notices displayed by works containing it; or + + c) Prohibiting misrepresentation of the origin of that material, or + requiring that modified versions of such material be marked in + reasonable ways as different from the original version; or + + d) Limiting the use for publicity purposes of names of licensors or + authors of the material; or + + e) Declining to grant rights under trademark law for use of some + trade names, trademarks, or service marks; or + + f) Requiring indemnification of licensors and authors of that + material by anyone who conveys the material (or modified versions of + it) with contractual assumptions of liability to the recipient, for + any liability that these contractual assumptions directly impose on + those licensors and authors. + + All other non-permissive additional terms are considered "further +restrictions" within the meaning of section 10. If the Program as you +received it, or any part of it, contains a notice stating that it is +governed by this License along with a term that is a further +restriction, you may remove that term. If a license document contains +a further restriction but permits relicensing or conveying under this +License, you may add to a covered work material governed by the terms +of that license document, provided that the further restriction does +not survive such relicensing or conveying. + + If you add terms to a covered work in accord with this section, you +must place, in the relevant source files, a statement of the +additional terms that apply to those files, or a notice indicating +where to find the applicable terms. + + Additional terms, permissive or non-permissive, may be stated in the +form of a separately written license, or stated as exceptions; +the above requirements apply either way. + + 8. Termination. + + You may not propagate or modify a covered work except as expressly +provided under this License. Any attempt otherwise to propagate or +modify it is void, and will automatically terminate your rights under +this License (including any patent licenses granted under the third +paragraph of section 11). + + However, if you cease all violation of this License, then your +license from a particular copyright holder is reinstated (a) +provisionally, unless and until the copyright holder explicitly and +finally terminates your license, and (b) permanently, if the copyright +holder fails to notify you of the violation by some reasonable means +prior to 60 days after the cessation. + + Moreover, your license from a particular copyright holder is +reinstated permanently if the copyright holder notifies you of the +violation by some reasonable means, this is the first time you have +received notice of violation of this License (for any work) from that +copyright holder, and you cure the violation prior to 30 days after +your receipt of the notice. + + Termination of your rights under this section does not terminate the +licenses of parties who have received copies or rights from you under +this License. If your rights have been terminated and not permanently +reinstated, you do not qualify to receive new licenses for the same +material under section 10. + + 9. Acceptance Not Required for Having Copies. + + You are not required to accept this License in order to receive or +run a copy of the Program. Ancillary propagation of a covered work +occurring solely as a consequence of using peer-to-peer transmission +to receive a copy likewise does not require acceptance. However, +nothing other than this License grants you permission to propagate or +modify any covered work. These actions infringe copyright if you do +not accept this License. Therefore, by modifying or propagating a +covered work, you indicate your acceptance of this License to do so. + + 10. Automatic Licensing of Downstream Recipients. + + Each time you convey a covered work, the recipient automatically +receives a license from the original licensors, to run, modify and +propagate that work, subject to this License. You are not responsible +for enforcing compliance by third parties with this License. + + An "entity transaction" is a transaction transferring control of an +organization, or substantially all assets of one, or subdividing an +organization, or merging organizations. If propagation of a covered +work results from an entity transaction, each party to that +transaction who receives a copy of the work also receives whatever +licenses to the work the party's predecessor in interest had or could +give under the previous paragraph, plus a right to possession of the +Corresponding Source of the work from the predecessor in interest, if +the predecessor has it or can get it with reasonable efforts. + + You may not impose any further restrictions on the exercise of the +rights granted or affirmed under this License. For example, you may +not impose a license fee, royalty, or other charge for exercise of +rights granted under this License, and you may not initiate litigation +(including a cross-claim or counterclaim in a lawsuit) alleging that +any patent claim is infringed by making, using, selling, offering for +sale, or importing the Program or any portion of it. + + 11. Patents. + + A "contributor" is a copyright holder who authorizes use under this +License of the Program or a work on which the Program is based. The +work thus licensed is called the contributor's "contributor version". + + A contributor's "essential patent claims" are all patent claims +owned or controlled by the contributor, whether already acquired or +hereafter acquired, that would be infringed by some manner, permitted +by this License, of making, using, or selling its contributor version, +but do not include claims that would be infringed only as a +consequence of further modification of the contributor version. For +purposes of this definition, "control" includes the right to grant +patent sublicenses in a manner consistent with the requirements of +this License. + + Each contributor grants you a non-exclusive, worldwide, royalty-free +patent license under the contributor's essential patent claims, to +make, use, sell, offer for sale, import and otherwise run, modify and +propagate the contents of its contributor version. + + In the following three paragraphs, a "patent license" is any express +agreement or commitment, however denominated, not to enforce a patent +(such as an express permission to practice a patent or covenant not to +sue for patent infringement). To "grant" such a patent license to a +party means to make such an agreement or commitment not to enforce a +patent against the party. + + If you convey a covered work, knowingly relying on a patent license, +and the Corresponding Source of the work is not available for anyone +to copy, free of charge and under the terms of this License, through a +publicly available network server or other readily accessible means, +then you must either (1) cause the Corresponding Source to be so +available, or (2) arrange to deprive yourself of the benefit of the +patent license for this particular work, or (3) arrange, in a manner +consistent with the requirements of this License, to extend the patent +license to downstream recipients. "Knowingly relying" means you have +actual knowledge that, but for the patent license, your conveying the +covered work in a country, or your recipient's use of the covered work +in a country, would infringe one or more identifiable patents in that +country that you have reason to believe are valid. + + If, pursuant to or in connection with a single transaction or +arrangement, you convey, or propagate by procuring conveyance of, a +covered work, and grant a patent license to some of the parties +receiving the covered work authorizing them to use, propagate, modify +or convey a specific copy of the covered work, then the patent license +you grant is automatically extended to all recipients of the covered +work and works based on it. + + A patent license is "discriminatory" if it does not include within +the scope of its coverage, prohibits the exercise of, or is +conditioned on the non-exercise of one or more of the rights that are +specifically granted under this License. You may not convey a covered +work if you are a party to an arrangement with a third party that is +in the business of distributing software, under which you make payment +to the third party based on the extent of your activity of conveying +the work, and under which the third party grants, to any of the +parties who would receive the covered work from you, a discriminatory +patent license (a) in connection with copies of the covered work +conveyed by you (or copies made from those copies), or (b) primarily +for and in connection with specific products or compilations that +contain the covered work, unless you entered into that arrangement, +or that patent license was granted, prior to 28 March 2007. + + Nothing in this License shall be construed as excluding or limiting +any implied license or other defenses to infringement that may +otherwise be available to you under applicable patent law. + + 12. No Surrender of Others' Freedom. + + If conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot convey a +covered work so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you may +not convey it at all. For example, if you agree to terms that obligate you +to collect a royalty for further conveying from those to whom you convey +the Program, the only way you could satisfy both those terms and this +License would be to refrain entirely from conveying the Program. + + 13. Use with the GNU Affero General Public License. + + Notwithstanding any other provision of this License, you have +permission to link or combine any covered work with a work licensed +under version 3 of the GNU Affero General Public License into a single +combined work, and to convey the resulting work. The terms of this +License will continue to apply to the part which is the covered work, +but the special requirements of the GNU Affero General Public License, +section 13, concerning interaction through a network will apply to the +combination as such. + + 14. Revised Versions of this License. + + The Free Software Foundation may publish revised and/or new versions of +the GNU General Public License from time to time. Such new versions will +be similar in spirit to the present version, but may differ in detail to +address new problems or concerns. + + Each version is given a distinguishing version number. If the +Program specifies that a certain numbered version of the GNU General +Public License "or any later version" applies to it, you have the +option of following the terms and conditions either of that numbered +version or of any later version published by the Free Software +Foundation. If the Program does not specify a version number of the +GNU General Public License, you may choose any version ever published +by the Free Software Foundation. + + If the Program specifies that a proxy can decide which future +versions of the GNU General Public License can be used, that proxy's +public statement of acceptance of a version permanently authorizes you +to choose that version for the Program. + + Later license versions may give you additional or different +permissions. However, no additional obligations are imposed on any +author or copyright holder as a result of your choosing to follow a +later version. + + 15. Disclaimer of Warranty. + + THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY +APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT +HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY +OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, +THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM +IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF +ALL NECESSARY SERVICING, REPAIR OR CORRECTION. + + 16. Limitation of Liability. + + IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING +WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MODIFIES AND/OR CONVEYS +THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY +GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE +USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF +DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD +PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), +EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF +SUCH DAMAGES. + + 17. Interpretation of Sections 15 and 16. + + If the disclaimer of warranty and limitation of liability provided +above cannot be given local legal effect according to their terms, +reviewing courts shall apply local law that most closely approximates +an absolute waiver of all civil liability in connection with the +Program, unless a warranty or assumption of liability accompanies a +copy of the Program in return for a fee. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Programs + + If you develop a new program, and you want it to be of the greatest +possible use to the public, the best way to achieve this is to make it +free software which everyone can redistribute and change under these terms. + + To do so, attach the following notices to the program. It is safest +to attach them to the start of each source file to most effectively +state the exclusion of warranty; and each file should have at least +the "copyright" line and a pointer to where the full notice is found. + + <one line to give the program's name and a brief idea of what it does.> + Copyright (C) <year> <name of author> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + +Also add information on how to contact you by electronic and paper mail. + + If the program does terminal interaction, make it output a short +notice like this when it starts in an interactive mode: + + <program> Copyright (C) <year> <name of author> + This program comes with ABSOLUTELY NO WARRANTY; for details type `show w'. + This is free software, and you are welcome to redistribute it + under certain conditions; type `show c' for details. + +The hypothetical commands `show w' and `show c' should show the appropriate +parts of the General Public License. Of course, your program's commands +might be different; for a GUI interface, you would use an "about box". + + You should also get your employer (if you work as a programmer) or school, +if any, to sign a "copyright disclaimer" for the program, if necessary. +For more information on this, and how to apply and follow the GNU GPL, see +<https://www.gnu.org/licenses/>. + + The GNU General Public License does not permit incorporating your program +into proprietary programs. If your program is a subroutine library, you +may consider it more useful to permit linking proprietary applications with +the library. If this is what you want to do, use the GNU Lesser General +Public License instead of this License. But first, please read +<https://www.gnu.org/licenses/why-not-lgpl.html>. @@ -0,0 +1,83 @@ +asm.sh +====== + +asm.sh is an assembler embedded into POSIX shell. It defines functions for +all (supported) i386 instructions. + +It generally follows AT&T syntax, modified in many places to avoid characters +reserved by the shell. Arguments are separated by spaces, no comma allowed +(as usual in shell). Width suffixes are generally mandatory. + +Labels +------ + +There are two kinds of label: Global and local labels. + +Global labels are defined with the `label' function, e.g.: + +label _start + +They must be globally unique. Global labels are referred to by their name, +e.g. `_start'. + +They can also be relative; the following defines a label `offset' whose value +is the difference between the current location and the value of the label +`base': + +label offset base + +Local labels are defined with the `L' function, e.g.: + +L loop + +There can be several definitions of a local label. There are two ways to +refer to a local label: + +- `loop^' refers to the previous declaration of the label +- `loop.' refers to the next declaration of the label + +Operands +-------- + +Immediates: Either a label, or an integer literal in decimal, octal +(preceded by 0) or hexadecimal (preceded by 0x). + +Registers: Preceded by `%' as in AT&T, e.g. `%eax'. + +Memory operands: Start with `@', followed by a sum expression. Examples: + + AT&T | asm.sh + -------------------|------------------- + 0x100 | @0x100 + label | @label + 4(%eax) | @%eax+4 + 4(,%eax) | @1%eax+4 + 14(,%eax,2) | @14+2%eax + (%eax,%ebx) | @%eax+%ebx + (%ebx,%eax) | @%ebx+%eax + (%ebx,%eax) | @1%eax+%ebx + 12(%ebx,%eax,8) | @%ebx+8%eax+12 + + The order of the summands is generally irrelevant, except that if there are + two unscaled registers, the first is taken to be the base and the second + the index. Displacement can be a label, scale must be one of the literal + characters 1, 2, 4, or 8 (or omitted, implicitly 1). + +Calling convention +================== + +The first three arguments are passed in %eax, %ecx and %edx. Remaining +arguments are passed on the stack in right-to-left order (last argument is +pushed first), and cleaned up by the callee. + +The return value currently always fits in three registers; it is placed in +%eax, %ecx, and %edx. Some functions also modify EFLAGS, e.g. streq sets +ZF iff the strings are equal. + +Functions may clobber %eax, %ecx and %edx. Stack must be 4-byte aligned. + +Porting +======= + +To port to other operating systems, it should be sufficient to modify asm.sh +(for the ELF header) and start.asm (for system calls etc). diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..182037f --- /dev/null +++ b/Makefile @@ -0,0 +1,6 @@ +sysf: FORCE + sh main.sh > sysf + chmod a+x sysf + +FORCE: +.PHONY: FORCE @@ -0,0 +1,101 @@ +sysf-i386 +========= + +sysf-i386 is an implementation of System F in i386 assembly language. + +Building +-------- + +Type `make' to build the executable (named `sysf'). The executable is a Linux +ELF binary. Only a POSIX shell should be required for the build. (In +particular, an assembler is not required.) + +The build process is a bit slow, it takes about a minute on my machine. + +Syntax +------ + +Names are made up of Latin letters, digits, and underscores. + +Function types are written with an arrow ->, which is right-associative, +i.e. a -> b -> c is the same as a -> (b -> c). Quantification is written +with an ASCII simplification of a forall symbol \/. There is no delimiter +between the quantified type variable and the body of the quantifier. + +type ::= NAME + | type '->' type + | '\/' NAME type + | '(' type ')' + +Term lambda terms are written with an ASCII simplification of a lower case +lambda \. Type lambda terms are written with an ASCII simplification of an +upper case lambda /\. Application are implicit. + +term ::= NAME + | '\' NAME ':' type term ; term lambda abstraction + | '/\' NAME term ; type lambda abstraction + | term term ; application + | '(' term ')' + +Application is left-associative, i.e. a b c is the same as (a b) c. Lambda +terms (both kinds) extend as far to the right as possible, i.e. (a \x:t b) c +is the same as (a (\x:t b)) c. + +To make the requirement of explicit type annotations more bearable, type +macros are supported. A type macro is defined on a line of its own, starting +with an octothorpe: + +#Bool \/X X->X->X + +From this point on, Bool can be used as a type. Type macros can also be +parameterised: + +#Function[x y] x->y + +Now, for example, Function[Bool Bool] refers to a function from Bool to Bool. +Macros may be redefined, later definition override earlier ones. Macro +expansion is hygienic. + +Comments start with a semicolon and continue until the end of the line. + +Evaluation +---------- + +sysf-i386 uses call-by-need evalution. Since the implementation is not very +smart, major space leaks may occur. + +Input and output +---------------- + +Input and output is done bit by bit, LSB first. + +Effects are modeled by an algebra of actions. The type of actions is usually +denoted as IO. The following operators are available: + +fix: \/X ((X->IO)->(X->IO))->(X->IO) + A loop. + fix T f reduces to f (fix T f). +read: IO -> IO -> IO -> IO + Try to read a single bit of input. Then: + - If no more input is available, run the first argument. + - If a 0 bit was read, run the second argument + - If a 1 bit was read, run the third argument + Just like read(2), even if one read call indicates end of input, subsequent + read calls may produce more input (e.g. if input is from a terminal). +write0 : IO -> IO + Write a 0 bit, then run the argument. +write1 : IO -> IO + Write a 1 bit, then run the argument. +exit : IO + Exit the program. + +These operators are supplied as functions. Accordingly, the type of the entire +program must be: + +\/IO + (\/X ((X->IO)->(X->IO))->(X->IO)) -> ; fix + (IO->IO->IO->IO) -> ; read + (IO->IO) -> ; write0 + (IO->IO) -> ; write1 + IO -> ; exit + IO @@ -0,0 +1,1133 @@ +# Copyright (C) 2026 Sebastian G. Kirmayer <gloria@gloria-mundi.eu> +# +# This file is part of sysf-i386. +# +# sysf-i386 is free software: you can redistribute it and/or modify it under +# the terms of the GNU General Public License as published by the Free +# Software Foundation, either version 3 of the License, or (at your option) +# any later version. +# +# sysf-i386 is distributed in the hope that it will be useful, but WITHOUT ANY +# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS +# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more +# details. +# +# You should have received a copy of the GNU General Public License along +# with sysf-i386. If not, see <https://www.gnu.org/licenses/>. +# + +LC_ALL=POSIX + +_asm_cc() { + _asm_ccval=0 + for _asm_ccs in o no "b c nae" "nb nc ae" "e z" "ne nz" "be na" "nbe a" \ + s ns "p pe" "np po" "l nge" "nl ge" "le ng" "nle g" + do + for _asm_cc in $_asm_ccs + do + eval "$1$_asm_cc() { _asm_$1 $_asm_ccval \"\$@\" ; }" + done + : $(( _asm_ccval += 1 )) + done +} + +addl() { + _asm_src "$1" + _asm_dst "$2" + case $_asm_src/$_asm_dst in + imm/reg|imm/mem) + if [ $(( -0x80 <= _asm_src_imm && _asm_src_imm < 0x80 )) != 0 ] + then + byte 0x83 + _asm_modrm 0 _asm_dst + byte $_asm_src_imm + elif [ $_asm_dst = reg ] && [ $_asm_dst_reg = 0 ] + then + byte 0x05 + long $_asm_src_imm + else + byte 0x81 + _asm_modrm 0 _asm_dst + long $_asm_src_imm + fi + ;; + reg/reg|reg/mem) + byte 0x01 + _asm_modrm $_asm_src_reg _asm_dst + ;; + reg/reg|mem/reg) + byte 0x03 + _asm_modrm $_asm_dst_reg _asm_src + ;; + *) + _asm_panic "addl $_asm_src $_asm_dst: unsupported" + esac +} + +andl() { + _asm_src "$1" + _asm_dst "$2" + case $_asm_src/$_asm_dst/$_asm_dst_reg in + imm/reg/0) + byte 0x25 + long $_asm_src_imm + ;; + imm/reg/*|imm/mem/*) + byte 0x81 + _asm_modrm 4 _asm_dst + long $_asm_src_imm + ;; + reg/reg/*|reg/mem/*) + byte 0x21 + _asm_modrm $_asm_src_reg _asm_dst + ;; + reg/reg/*|mem/reg/*) + byte 0x23 + _asm_modrm $_asm_dst_reg _asm_src + ;; + *) + _asm_panic "andl $_asm_src $_asm_dst: unsupported" + esac +} + +cmpb() { + _asm_src8 "$1" + _asm_dst8 "$2" + case $_asm_src/$_asm_dst/$_asm_dst_reg in + imm/reg/0) + byte 0x3C + byte $_asm_src_imm + ;; + imm/reg/*|imm/mem/*) + byte 0x80 + _asm_modrm 7 _asm_dst + byte $_asm_src_imm + ;; + reg/reg|reg/mem) + byte 0x38 + _asm_modrm $_asm_src_reg _asm_dst + ;; + reg/reg|mem/reg) + byte 0x3A + _asm_modrm $_asm_dst_reg _asm_src + ;; + *) + _asm_panic "cmpb $_asm_src $_asm_dst: unsupported" + esac +} + +cmpl() { + _asm_src "$1" + _asm_dst "$2" + case $_asm_src/$_asm_dst in + imm/reg|imm/mem) + if [ $(( -0x80 <= _asm_src_imm && _asm_src_imm < 0x80 )) != 0 ] + then + byte 0x83 + _asm_modrm 7 _asm_dst + byte $_asm_src_imm + elif [ $_asm_dst = reg ] && [ $_asm_dst_reg = 0 ] + then + byte 0x3D + long $_asm_src_imm + else + byte 0x81 + _asm_modrm 7 _asm_dst + long $_asm_src_imm + fi + ;; + reg/reg|reg/mem) + byte 0x39 + _asm_modrm $_asm_src_reg _asm_dst + ;; + reg/reg|mem/reg) + byte 0x3B + _asm_modrm $_asm_dst_reg _asm_src + ;; + *) + _asm_panic "cmpl $_asm_src $_asm_dst: unsupported" + esac +} + +cmpsb() { + byte 0xA6 +} + +call() { + _asm_dst "$1" + case $_asm_dst in + reg|mem) + byte 0xFF + _asm_modrm 2 _asm_dst + return + ;; + imm) + ;; + *) + _asm_panic "call $_asm_dst: unsupported" + esac + + _asm_jmp_dist=$(( _asm_dst_imm - _asm_offset )) + byte 0xE8 + long $((_asm_jmp_dist-5)) +} + +_asm_cc cmov +_asm_cmov() { + _asm_src "$2" + _asm_dst "$3" + case $_asm_src/$_asm_dst in + reg/reg|mem/reg) + byte 0x0F + byte $(( 0x40 | $1 )) + _asm_modrm $_asm_dst_reg _asm_src + ;; + *) + _asm_panic "cmov $_asm_src $_asm_dst: unsupported" + esac +} + +decl() { + _asm_dst "$1" + case $_asm_dst in + reg) + byte $(( 0x48 | _asm_dst_reg )) + ;; + reg|mem) + byte 0xFF + _asm_modrm 1 _asm_dst + ;; + *) + _asm_panic "decl $_asm_dst: unsupported" + esac +} + +divl() { + _asm_src "$1" + case $_asm_src in + reg|mem) + byte 0xF7 + _asm_modrm 6 _asm_src + ;; + *) + _asm_panic "divl $_asm_src: unsupported" + esac +} + +incl() { + _asm_dst "$1" + case $_asm_dst in + reg) + byte $(( 0x40 | _asm_dst_reg )) + ;; + reg|mem) + byte 0xFF + _asm_modrm 0 _asm_dst + ;; + *) + _asm_panic "incl $_asm_dst: unsupported" + esac +} + +incb() { + _asm_dst8 "$1" + case $_asm_dst in + reg|mem) + byte 0xFE + _asm_modrm 0 _asm_dst + ;; + *) + _asm_panic "incb $_asm_dst: unsupported" + esac +} + +int() { + byte 0xCD + byte "$1" +} + +int3() { + byte 0xCC +} + +_asm_cc j +_asm_j() { + _asm_eval "$2" + _asm_jmp_dist=$(( _asm_value - _asm_offset )) + if [ $(( -0x80 <= _asm_jmp_dist-2 && _asm_jmp_dist-2 < 0x80 )) != 0 ] + then + byte $(( 0x70 | $1 )) + byte $((_asm_jmp_dist-2)) + else + byte 0x0F + byte $(( 0x80 | $1 )) + long $((_asm_jmp_dist-6)) + fi +} + +jmp() { + _asm_dst "$1" + case $_asm_dst in + reg|mem) + byte 0xFF + _asm_modrm 4 _asm_dst + return + ;; + imm) + ;; + *) + _asm_panic "jmp $_asm_dst: unsupported" + esac + + _asm_jmp_dist=$(( _asm_dst_imm - _asm_offset )) + if [ $(( -0x80 <= _asm_jmp_dist-2 && _asm_jmp_dist-2 < 0x80 )) != 0 ] + then + byte 0xEB + byte $((_asm_jmp_dist-2)) + else + byte 0xE9 + long $((_asm_jmp_dist-5)) + fi +} + +leal() { + _asm_src "$1" + _asm_dst "$2" + case $_asm_src/$_asm_dst in + mem/reg) + byte 0x8D + _asm_modrm $_asm_dst_reg _asm_src + ;; + *) + _asm_panic "leal $_asm_src $_asm_dst: unsupported" + esac +} + +movb() { + _asm_src8 "$1" + _asm_dst8 "$2" + case $_asm_src/$_asm_dst in + reg/reg|reg/mem) + byte 0x88 + _asm_modrm $_asm_src_reg _asm_dst + ;; + reg/reg|mem/reg) + byte 0x8A + _asm_modrm $_asm_dst_reg _asm_src + ;; + imm/reg) + byte $(( 0xB0 | _asm_dst_reg )) + byte $_asm_src_imm + ;; + imm/reg|imm/mem) + byte 0xC6 + _asm_modrm 0 _asm_dst + byte $_asm_src_imm + ;; + *) + _asm_panic "movb $_asm_src $_asm_dst: unsupported" + esac +} + +movl() { + _asm_src "$1" + _asm_dst "$2" + case $_asm_src/$_asm_dst in + reg/reg|reg/mem) + byte 0x89 + _asm_modrm $_asm_src_reg _asm_dst + ;; + reg/reg|mem/reg) + byte 0x8B + _asm_modrm $_asm_dst_reg _asm_src + ;; + imm/reg) + byte $(( 0xB8 | _asm_dst_reg )) + long $_asm_src_imm + ;; + imm/reg|imm/mem) + byte 0xC7 + _asm_modrm 0 _asm_dst + long $_asm_src_imm + ;; + *) + _asm_panic "movl $_asm_src $_asm_dst: unsupported" + esac +} + +mull() { + _asm_src "$1" + case $_asm_src in + reg|mem) + byte 0xF7 + _asm_modrm 4 _asm_src + ;; + *) + _asm_panic "mull $_asm_src: unsupported" + esac +} + +negl() { + _asm_dst "$1" + case $_asm_dst in + reg|mem) + byte 0xF7 + _asm_modrm 3 _asm_dst + ;; + *) + _asm_panic "negl $_asm_dst: unsupported" + esac +} + +nop() { + byte 0x90 +} + +notl() { + _asm_dst "$1" + case $_asm_dst in + reg|mem) + byte 0xF7 + _asm_modrm 2 _asm_dst + ;; + *) + _asm_panic "notl $_asm_dst: unsupported" + esac +} + +orl() { + _asm_src "$1" + _asm_dst "$2" + case $_asm_src/$_asm_dst in + imm/reg|imm/mem) + if [ $(( -0x80 <= _asm_src_imm && _asm_src_imm < 0x80 )) != 0 ] + then + byte 0x83 + _asm_modrm 1 _asm_dst + byte $_asm_src_imm + elif [ $_asm_dst = reg ] && [ $_asm_dst_reg = 0 ] + then + byte 0x0D + long $_asm_src_imm + else + byte 0x81 + _asm_modrm 1 _asm_dst + long $_asm_src_imm + fi + ;; + reg/reg|reg/mem) + byte 0x09 + _asm_modrm $_asm_src_reg _asm_dst + ;; + reg/reg|mem/reg) + byte 0x0B + _asm_modrm $_asm_dst_reg _asm_src + ;; + *) + _asm_panic "orl $_asm_src $_asm_dst: unsupported" + esac +} + +orb() { + _asm_src8 "$1" + _asm_dst8 "$2" + case $_asm_src/$_asm_dst in + imm/reg|imm/mem) + if [ $_asm_dst = reg ] && [ $_asm_dst_reg = 0 ] + then + byte 0x0C + long $_asm_src_imm + else + byte 0x80 + _asm_modrm 1 _asm_dst + long $_asm_src_imm + fi + ;; + reg/reg|reg/mem) + byte 0x08 + _asm_modrm $_asm_src_reg _asm_dst + ;; + reg/reg|mem/reg) + byte 0x0A + _asm_modrm $_asm_dst_reg _asm_src + ;; + *) + _asm_panic "orb $_asm_src $_asm_dst: unsupported" + esac +} + +popl() { + _asm_dst "$1" + case $_asm_dst in + reg) + byte $((0x58 | _asm_dst_reg)) + ;; + reg|mem) + byte 0x8F + _asm_modrm 0 _asm_dst + ;; + *) + _asm_panic "popl $_asm_src: unsupported" + esac +} + +pushl() { + _asm_src "$1" + case $_asm_src in + reg) + byte $((0x50 | _asm_src_reg)) + ;; + reg|mem) + byte 0xFF + _asm_modrm 6 _asm_src + ;; + imm) + byte 0x68 + long $_asm_src_imm + ;; + *) + _asm_panic "pushl $_asm_src: unsupported" + esac +} + +repnz() { + byte 0xF2 + "$@" +} + +repz() { + byte 0xF3 + "$@" +} + +ret() { + if [ $# -eq 0 ] + then + byte 0xC3 + else + byte 0xC2 + word "$1" + fi +} + +scasb() { + byte 0xAE +} + +shll() { + _asm_src8 "$1" + _asm_dst "$2" + case $_asm_src/$_asm_src_reg/$_asm_dst in + imm/*/reg|imm/*/mem) + if [ $_asm_src_imm = 1 ] ; then + byte 0xD1 + _asm_modrm 4 _asm_dst + else + byte 0xC1 + _asm_modrm 4 _asm_dst + byte $_asm_src_imm + fi + ;; + reg/1/reg|reg/1/mem) + byte 0xD3 + _asm_modrm 4 _asm_dst + ;; + *) + _asm_panic "shll $_asm_src $_asm_dst: unsupported" + esac +} + +shrl() { + _asm_src8 "$1" + _asm_dst "$2" + case $_asm_src/$_asm_src_reg/$_asm_dst in + imm/*/reg|imm/*/mem) + if [ $_asm_src_imm = 1 ] ; then + byte 0xD1 + _asm_modrm 5 _asm_dst + else + byte 0xC1 + _asm_modrm 5 _asm_dst + byte $_asm_src_imm + fi + ;; + reg/1/reg|reg/1/mem) + byte 0xD3 + _asm_modrm 5 _asm_dst + ;; + *) + _asm_panic "shrl $_asm_src $_asm_dst: unsupported" + esac +} + +subl() { + _asm_src "$1" + _asm_dst "$2" + case $_asm_src/$_asm_dst in + imm/reg|imm/mem) + if [ $(( -0x80 <= _asm_src_imm && _asm_src_imm < 0x80 )) != 0 ] + then + byte 0x83 + _asm_modrm 5 _asm_dst + byte $_asm_src_imm + elif [ $_asm_dst = reg ] && [ $_asm_dst_reg = 0 ] + then + byte 0x2D + long $_asm_src_imm + else + byte 0x81 + _asm_modrm 5 _asm_dst + long $_asm_src_imm + fi + ;; + reg/reg|reg/mem) + byte 0x29 + _asm_modrm $_asm_src_reg _asm_dst + ;; + reg/reg|mem/reg) + byte 0x2B + _asm_modrm $_asm_dst_reg _asm_src + ;; + *) + _asm_panic "subl $_asm_src $_asm_dst: unsupported" + esac +} + +test() { + _asm_panic "test requires width suffix" +} + +testl() { + _asm_src "$1" + _asm_dst "$2" + case $_asm_src/$_asm_dst/$_asm_dst_reg in + imm/reg/0) + byte 0xA9 + long $_asm_src_imm + ;; + imm/reg/*|imm/mem/*) + byte 0xF7 + _asm_modrm 0 _asm_dst + long $_asm_src_imm + ;; + reg/reg/*|reg/mem/*) + byte 0x85 + _asm_modrm $_asm_src_reg _asm_dst + ;; + *) + _asm_panic "testl $_asm_src $_asm_dst: unsupported" + esac +} + +ud2() { + byte 0x0F + byte 0x0B +} + +xchgl() { + _asm_src "$1" + _asm_dst "$2" + case $_asm_src/$_asm_dst/$_asm_src_reg/$_asm_dst_reg in + reg/reg/0/*) + byte $((0x90 + _asm_dst_reg)) + ;; + reg/reg/*/0) + byte $((0x90 + _asm_src_reg)) + ;; + reg/reg/*|mem/reg/*) + byte 0x87 + _asm_modrm $_asm_dst_reg _asm_src + ;; + reg/reg/*|reg/mem/*) + byte 0x87 + _asm_modrm $_asm_src_reg _asm_dst + ;; + *) + _asm_panic "xchgl $_asm_src $_asm_dst: unsupported" + esac +} + +xorl() { + _asm_src "$1" + _asm_dst "$2" + case $_asm_src/$_asm_dst in + imm/reg|imm/mem) + if [ $(( -0x80 <= _asm_src_imm && _asm_src_imm < 0x80 )) != 0 ] + then + byte 0x83 + _asm_modrm 6 _asm_dst + byte $_asm_src_imm + elif [ $_asm_dst = reg ] && [ $_asm_dst_reg = 0 ] + then + byte 0x35 + long $_asm_src_imm + else + byte 0x81 + _asm_modrm 6 _asm_dst + long $_asm_src_imm + fi + ;; + reg/reg|reg/mem) + byte 0x31 + _asm_modrm $_asm_src_reg _asm_dst + ;; + reg/reg|mem/reg) + byte 0x33 + _asm_modrm $_asm_dst_reg _asm_src + ;; + *) + _asm_panic "xorl $_asm_src $_asm_dst: unsupported" + esac +} + +byte() { + : $(( _asm_offset += 1 )) + _asm_eval "$1" + _asm_printf "\\$(printf %03o $(( _asm_value & 0xFF )))" +} + +word() { + _asm_eval "$1" + _asm_word=$_asm_value + byte $(( _asm_word )) + byte $(( _asm_word >> 8 )) +} + +long() { + _asm_eval "$1" + _asm_long=$_asm_value + word $(( _asm_long )) + word $(( _asm_long >> 16 )) +} + +align() { + _asm_align=${1-4} + skip $(( (_asm_align - (_asm_offset % _asm_align)) % _asm_align )) +} + +skip() { + _asm_eval "$1" + : $(( _asm_offset += _asm_value )) + if [ $_asm_active != 0 ] ; then + while [ $_asm_value -gt 0 ] ; do + printf '\0' + : $(( _asm_value -= 1 )) + done + fi +} + +ascii() { + : $(( _asm_offset += ${#1} )) + _asm_printf '%s' "$1" +} + +_asm_modrm() { + eval "_asm_modrm_rm=\$$2" + case $_asm_modrm_rm in + reg) + byte $(( 0xC0 | $1 << 3 | $2_reg )) + return + ;; + mem) + ;; + *) + _asm_panic "modrm $_asm_modrm_rm: unsupported" + esac + + for part in base index scale displ ; do + eval "_asm_modrm_$part=\$$2_mem_$part" + done + + if [ -z "$_asm_modrm_displ" ] && [ "$_asm_modrm_base" != 5 ] ; then + _asm_modrm_displsize=0 + elif [ $(( -128 <= _asm_modrm_displ && _asm_modrm_displ < 128 )) != 0 ] + then + _asm_modrm_displsize=1 + else + _asm_modrm_displsize=2 + fi + + if [ -z "$_asm_modrm_index" ] && [ "$_asm_modrm_base" != 4 ] ; then + if [ -z "$_asm_modrm_base" ] ; then + byte $(( $1 << 3 | 5 )) + _asm_modrm_displsize=2 + else + byte $(( _asm_modrm_displsize << 6 | $1 << 3 | _asm_modrm_base )) + fi + else + if [ -z "$_asm_modrm_base" ] ; then + byte $(( $1 << 3 | 4 )) + _asm_modrm_displsize=2 + _asm_modrm_base=5 + else + byte $(( _asm_modrm_displsize << 6 | $1 << 3 | 4 )) + fi + [ "$_asm_modrm_index" ] || _asm_modrm_index=4 + byte $(( _asm_modrm_scale << 6 | _asm_modrm_index << 3 | _asm_modrm_base )) + fi + case $_asm_modrm_displsize in + 0) + ;; + 1) + byte $((_asm_modrm_displ)) + ;; + 2) + long $((_asm_modrm_displ)) + ;; + esac +} + +_asm_src8() { + _asm_op8 "$1" "_asm_src$2" +} + +_asm_src() { + _asm_op "$1" "_asm_src$2" +} + +_asm_dst8() { + _asm_op8 "$1" _asm_dst +} + +_asm_dst() { + _asm_op "$1" _asm_dst +} + +_asm_op8() { + case "$1" in + %*) + eval "$2=reg" + _asm_register8 "${1#%}" "$2_reg" + ;; + @*) + eval "$2=mem" + _asm_memory "${1#@}" "$2_mem" + ;; + *) + eval "$2=imm" + _asm_eval "$1" + eval "$2_imm=\$_asm_value" + esac +} + +_asm_op() { + case "$1" in + %*) + eval "$2=reg" + _asm_register "${1#%}" "$2_reg" + ;; + @*) + eval "$2=mem" + _asm_memory "${1#@}" "$2_mem" + ;; + *) + eval "$2=imm" + _asm_eval "$1" + eval "$2_imm=\$_asm_value" + esac +} + +_asm_register8() { + case "$1" in + al) eval "$2=0" ;; + cl) eval "$2=1" ;; + dl) eval "$2=2" ;; + bl) eval "$2=3" ;; + ah) eval "$2=4" ;; + ch) eval "$2=5" ;; + dh) eval "$2=6" ;; + bh) eval "$2=7" ;; + *) _asm_panic "unknown register %$1" + esac +} + +_asm_register() { + case "$1" in + eax) eval "$2=0" ;; + ecx) eval "$2=1" ;; + edx) eval "$2=2" ;; + ebx) eval "$2=3" ;; + esp) eval "$2=4" ;; + ebp) eval "$2=5" ;; + esi) eval "$2=6" ;; + edi) eval "$2=7" ;; + *) _asm_panic "unknown register %$1" + esac +} + +_asm_memory() { + _asm_memory_base= + _asm_memory_index= + _asm_memory_scale= + _asm_memory_displ= + _asm_memory_arg="$1+" + while [ "$_asm_memory_arg" ] ; do + _asm_memory_head="${_asm_memory_arg%%+*}" + _asm_memory_arg="${_asm_memory_arg#*+}" + case "$_asm_memory_head" in + %*) + if [ -z "$_asm_memory_base" ] ; then + _asm_register "${_asm_memory_head#%}" _asm_memory_base + elif [ -z "$_asm_memory_index" ] ; then + _asm_register "${_asm_memory_head#%}" _asm_memory_index + _asm_memory_scale=0 + else + _asm_panic "more than two registers in address calculation" + fi + ;; + [1248]%*) + if [ -z "$_asm_memory_index" ] ; then + _asm_register "${_asm_memory_head#[1248]%}" _asm_memory_index + _asm_memory_scale1=0 + _asm_memory_scale2=1 + _asm_memory_scale4=2 + _asm_memory_scale8=3 + : $(( _asm_memory_scale = _asm_memory_scale${_asm_memory_head%%\%*} )) + else + _asm_panic "two index registers in address calculation" + fi + ;; + *%*) + _asm_panic "illegal scale ${_asm_memory_head%%\%}" + ;; + *) + _asm_eval "$_asm_memory_head" + if [ -z "$_asm_memory_displ" ] ; then + _asm_memory_displ="$_asm_value" + else + _asm_panic "two displacements in address calculation" + fi + esac + done + [ "$_asm_memory_index" != 4 ] || _asm_panic "cannot use %esp as index" + for part in base index scale displ ; do + eval "$2_$part=\"\$_asm_memory_$part\"" + done +} + +_asm_eval() { + _asm_dropminus="${1#-}" + case "$_asm_dropminus" in + 0x*) + case "${_asm_dropminus#0x}" in + *[!0-9A-Fa-f]*) + ;; + *) + : $(( _asm_value = $1 )) + return + esac + ;; + 0*) + case "$_asm_dropminus" in + *[!0-7]*) + ;; + *) + : $(( _asm_value = $1 )) + return + esac + ;; + *[!0-9]*) + ;; + *) + : $(( _asm_value = $1 )) + return + esac + case "$1" in + [!a-zA-Z_]*|*[!a-zA-Z0-9_]*) + ;; + *) + eval "_asm_value=\$_asm_label_$1" + if [ "$_asm_value$_asm_pass0" = "" ] ; then + _asm_panic "label $1 not declared" + fi + : $(( _asm_value = _asm_value )) + return + esac + case "$1" in + *^|*.) + _asm_eval_L="${1%[.^]}" + _asm_L $_asm_eval_L + : $(( _asm_eval_L_idx = _asm_L_${_asm_eval_L}_idx )) + case "$1" in + *.) : $(( _asm_eval_L_idx += 1 )) + esac + eval "_asm_value=\$_asm_L_${_asm_eval_L}_${_asm_eval_L_idx}" + if [ "$_asm_value$_asm_pass0" = "" ] ; then + _asm_panic "label $1 not declared" + fi + : $(( _asm_value = _asm_value )) + return + esac + _asm_panic "failed to parse value $1" +} + +_asm_panic() { + printf '%s\n' "$@" >&2 + exit 1 +} + +_asm_printf() { + if [ $_asm_active != 0 ] ; then printf "$@" ; fi +} + +_asm_start_elf=0 +_asm_mmap_min_addr=0x10000 +_asm_flags_text=0x1 # x +_asm_flags_rodata=0x4 # r +_asm_flags_data=0x6 # rw + +_asm_section() { + : $(( _asm_offset_$_asm_section = _asm_offset )) + _asm_section="$1" + : $(( _asm_offset = _asm_offset_$_asm_section )) + : $(( _asm_active = _asm_active_$_asm_section )) +} + +text() { _asm_section text ; } +rodata() { _asm_section rodata ; } +data() { _asm_section data ; } +bss() { _asm_section bss ; } + +_asm_set() { + : $(( _asm_set_new = ($2) )) + : $(( _asm_modified |= $1 != _asm_set_new )) + : $(( $1 = _asm_set_new )) +} + +label() { + eval "_asm_label_oldval=\$_asm_label_$1" + if [ "$_asm_pass0" ] && [ "$_asm_label_oldval" ] ; then + _asm_panic "redefinition of label $1" + fi + if [ $# -eq 1 ] + then + _asm_set _asm_label_$1 _asm_offset + else + _asm_eval "$2" + _asm_set _asm_label_$1 '_asm_offset - _asm_value' + fi +} + +_asm_L() { + [ $(( _asm_generation == _asm_L_$1_gen )) != 0 ] || { + : $(( _asm_L_$1_gen = _asm_generation )) + : $(( _asm_L_$1_idx = 0 )) + } +} + +L() { + _asm_L $1 + _asm_set _asm_L_$1_$((_asm_L_$1_idx += 1)) _asm_offset +} + +_asm_elf() { + _asm_section elf + byte 0x7F # magic number + ascii 'ELF' + byte 1 # 32-bit format + byte 1 # little endian + byte 1 # ELF version + byte 3 # Linux + skip 8 # padding + word 2 # executable + word 3 # x86 + long 1 # ELF version + long _start # entry point + long _asm_phoff # program header offset + long 0 # section header offset + long 0 # flags + word _asm_elfhdr_end # ELF header size + word 32 # program header entry size + word 4 # program header entry count + word 0 # section header entry size + word 0 # section header entry count + word 0 # section name string table index + label _asm_elfhdr_end + label _asm_phoff + for _asm_local_section in text rodata data ; do + : $(( _asm_local_section_length = + _asm_end_$_asm_local_section - _asm_start_$_asm_local_section )) + long 1 # PT_LOAD + long $(( _asm_foffset_$_asm_local_section )) # file offset + long $(( _asm_start_$_asm_local_section )) # virtual address + long 0 # physical address + long $_asm_local_section_length # size in file + if [ $_asm_local_section = data ] + then + long $(( _asm_end_bss - _asm_start_data )) + else + long $_asm_local_section_length # size in memory + fi + long $(( _asm_flags_$_asm_local_section )) # permission flags + long 0x1000 # alignment + done + # The PT_GNU_STACK segment is needed to avoid the kernel's + # read-implies-exec personality. + long 0x6474e551 # PT_GNU_STACK + long 0 # file offset + long 0 # virtual address + long 0 # physical address + long 0 # size in file + long 0 # size in memory + long 0x6 # read/write + long 0x1000 # alignment +} + +_asm_run() { + for _asm_local_section in elf text rodata data bss ; do + : $(( _asm_offset_$_asm_local_section = + _asm_start_$_asm_local_section )) + : $(( _asm_active_$_asm_local_section = 0 )) + done + for _asm_local_section in "$@" ; do + : $(( _asm_active_$_asm_local_section = 1 )) + done + _asm_section=text + : $(( _asm_offset = _asm_offset_$_asm_section )) + : $(( _asm_active = _asm_active_$_asm_section )) + + _asm_modified=0 + : $(( _asm_generation += 1 )) + _asm_elf + text + prog + + : $(( _asm_offset_$_asm_section = _asm_offset )) + + _asm_set _asm_end_elf _asm_offset_elf + : $(( _asm_offset = _asm_end_elf + _asm_mmap_min_addr )) + for _asm_local_section in text rodata data bss ; do + : $(( _asm_offset2 = _asm_offset + + (_asm_offset_$_asm_local_section - _asm_start_$_asm_local_section) )) + _asm_set _asm_start_$_asm_local_section _asm_offset + _asm_set _asm_end_$_asm_local_section _asm_offset2 + _asm_offset="$_asm_offset2" + [ "$_asm_local_section" = data ] || \ + : $(( _asm_offset += 0x1000 )) + done + + _asm_foffset=0 + for _asm_local_section in elf text rodata data ; do + _asm_set _asm_foffset_$_asm_local_section _asm_foffset + : $(( _asm_foffset = _asm_foffset + + (_asm_end_$_asm_local_section - _asm_start_$_asm_local_section) )) + done +} + + +_asm_pass0=y +_asm_run +_asm_pass0= +_asm_limit=20 +while [ $_asm_modified -eq 1 ] ; do + _asm_run + : $(( _asm_limit -= 1 )) + if [ $_asm_limit -eq 0 ] ; then + _asm_panic "pass limit exceeded, failed to converge" + fi +done + +_asm_file_offset=0 +for _asm_top_section in elf text rodata data ; do + _asm_run $_asm_top_section +done diff --git a/eval.asm b/eval.asm new file mode 100644 index 0000000..15a9c2a --- /dev/null +++ b/eval.asm @@ -0,0 +1,258 @@ +# Copyright (C) 2026 Sebastian G. Kirmayer <gloria@gloria-mundi.eu> +# +# This file is part of sysf-i386. +# +# sysf-i386 is free software: you can redistribute it and/or modify it under +# the terms of the GNU General Public License as published by the Free +# Software Foundation, either version 3 of the License, or (at your option) +# any later version. +# +# sysf-i386 is distributed in the hope that it will be useful, but WITHOUT ANY +# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS +# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more +# details. +# +# You should have received a copy of the GNU General Public License along +# with sysf-i386. If not, see <https://www.gnu.org/licenses/>. +# + +rodata +align +L s + long s^ + long $VAL_FIX + long s^ + long $VAL_ABS +label term_fix + +L s + long s^ + long $VAL_READ + long s^ + long $VAL_ABS + long s^ + long $VAL_ABS + long s^ + long $VAL_ABS +label term_read + +L s + long s^ + long $VAL_WRITE0 + long s^ + long $VAL_ABS +label term_write0 + +L s + long s^ + long $VAL_WRITE1 + long s^ + long $VAL_ABS +label term_write1 + +L s + long s^ + long $VAL_EXIT +label term_exit + +bss +align +label alloc_next + long 0 + +data +align +label context_root + long 0 + long 0 + long 0 + long 0x10 + +# Context elements: +# 0: parent +# 4: context +# 8: term +# 12: refcount + +text +label execute + pushl 0 + pushl term_exit + pushl context_root + pushl 0 + pushl term_write1 + pushl context_root + pushl 0 + pushl term_write0 + pushl context_root + pushl 0 + pushl term_read + pushl context_root + pushl 0 + pushl term_fix + pushl context_root + pushl 0 + pushl %eax + pushl context_root + +L exec_loop + movl @%esp+4 %eax + movl @%eax+-4 %ebx + testl %ebx %ebx + js special. + +L var + movl @%esp %esi +L loop + decl %ebx %ebx + js done. + movl @%esi %esi + jmp loop^ +L done + # %esi -- variable context + movl @%esi+8 %edi + # %edi -- new term + cmpl $VAL_ABS @%edi+-4 + je no_writeback. + movl @%esp+8 %ebx + # %ebx -- old writeback + testl %ebx %ebx + jz no_old_writeback. + # write current value back + movl @%ebx+4 %eax + call unref + movl @%esp %ecx + incl @%ecx+12 + movl %ecx @%ebx+4 + movl @%esp+4 %ecx + movl %ecx @%ebx+8 + movl %ebx %eax + call unref +L no_old_writeback + incl @%esi+12 + movl %esi @%esp+8 +L no_writeback + movl %edi @%esp+4 + movl @%esi+4 %eax + incl @%eax+12 + xchgl %eax @%esp + call unref + jmp exec_loop^ + +L special + cmpl $VAL_APP %ebx + je app. + cmpl $VAL_ABS %ebx + je abs. + cmpl $VAL_FIX %ebx + je fix. + cmpl $VAL_READ %ebx + je read. + cmpl $VAL_WRITE0 %ebx + je write0. + cmpl $VAL_WRITE1 %ebx + je write1. + cmpl $VAL_EXIT %ebx + je exit + ud2 + +L app + pushl 0 + subl 8 %eax + movl %eax @%esp+8 + pushl @%eax+-8 + movl @%esp+8 %eax + incl @%eax+12 + pushl %eax + jmp exec_loop^ + +L abs + popl %ebx + popl %ebp + popl %edi + # %ebx -- context + # %ebp -- term + # %edi -- writeback + testl %edi %edi + jz no_writeback. + movl @%edi+4 %eax + call unref + incl @%ebx+12 + movl %ebx @%edi+4 + movl %ebp @%edi+8 + movl %edi %eax + call unref +L no_writeback + movl @alloc_next %eax + testl %eax %eax + jz no_next. + movl @%eax %ecx + movl %ecx @alloc_next +L have_ctx + movl %ebx @%eax + movl @%esp %ecx + movl %ecx @%eax+4 + movl @%esp+4 %ecx + movl %ecx @%eax+8 + movl 1 @%eax+12 + movl %eax @%esp + subl 8 %ebp + movl %ebp @%esp+4 + jmp exec_loop^ + +L no_next + movl @heap_ptr %esi + movl %esi %eax + addl 16 %esi + movl %esi @heap_ptr + cmpl @heap_end %esi + ja realloc. + jmp have_ctx^ +L realloc + movl %eax %esi + call alloc + movl %esi %eax + jmp have_ctx^ + +L fix + movl @%esp %eax + incl @%eax+12 + pushl %eax + pushl @%eax+8 + movl @%eax+4 %eax + incl @%eax+12 + pushl %eax + jmp exec_loop^ + +L read + call read + movl 1 %ebx + subl %eax %ebx + jmp var^ + +L write0 + call write0 + xorl %ebx %ebx + jmp var^ + +L write1 + call write1 + xorl %ebx %ebx + jmp var^ + +label unref + decl @%eax+12 + jz free. + ret +L free + pushl %eax + movl @%eax %eax + call unref + movl @%esp %eax + movl @%eax+4 %eax + call unref + popl %eax + movl @alloc_next %ecx + movl %eax @alloc_next + movl %ecx @%eax + ret diff --git a/examples/cat.sysf b/examples/cat.sysf new file mode 100644 index 0000000..84ab121 --- /dev/null +++ b/examples/cat.sysf @@ -0,0 +1,19 @@ +; cat -- echo back input +; +; This program echoes its input back to stdout until end of file is reached. + +; Copyright (C) 2026 Sebastian G. Kirmayer <gloria@gloria-mundi.eu> +; +; Permission to use, copy, modify, and/or distribute this software for any +; purpose with or without fee is hereby granted. +; +; 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. + +/\IO\fix:\/X((X->IO)->X->IO)->X->IO\read:IO->IO->IO->IO\write0:IO->IO\write1:IO->IO\exit:IO +fix IO (\f:IO->IO \_:IO read exit (write0 (f _)) (write1 (f _))) exit diff --git a/examples/hello.sysf b/examples/hello.sysf new file mode 100644 index 0000000..7b300fb --- /dev/null +++ b/examples/hello.sysf @@ -0,0 +1,54 @@ +; hello -- friendly greeting program +; +; Print a friendly, non-customizable greeting. + +; Copyright (C) 2026 Sebastian G. Kirmayer <gloria@gloria-mundi.eu> +; +; Permission to use, copy, modify, and/or distribute this software for any +; purpose with or without fee is hereby granted. +; +; 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. + +/\IO\fix:\/X((X->IO)->X->IO)->X->IO\read:IO->IO->IO->IO\write0:IO->IO\write1:IO->IO\exit:IO + +(\m:(IO->IO)->IO m + \r:IO write0 (write0 (write0 (write1 (write0 (write0 (write1 (write0 r))))))) +)\H:IO->IO +(\m:(IO->IO)->IO m + \r:IO write1 (write0 (write1 (write0 (write0 (write1 (write1 (write0 r))))))) +)\e:IO->IO +(\m:(IO->IO)->IO m + \r:IO write0 (write0 (write1 (write1 (write0 (write1 (write1 (write0 r))))))) +)\l:IO->IO +(\m:(IO->IO)->IO m + \r:IO write1 (write1 (write1 (write1 (write0 (write1 (write1 (write0 r))))))) +)\o:IO->IO +(\m:(IO->IO)->IO m + \r:IO write0 (write0 (write1 (write1 (write0 (write1 (write0 (write0 r))))))) +)\comma:IO->IO +(\m:(IO->IO)->IO m + \r:IO write0 (write0 (write0 (write0 (write0 (write1 (write0 (write0 r))))))) +)\space:IO->IO +(\m:(IO->IO)->IO m + \r:IO write1 (write1 (write1 (write0 (write1 (write1 (write1 (write0 r))))))) +)\w:IO->IO +(\m:(IO->IO)->IO m + \r:IO write0 (write1 (write0 (write0 (write1 (write1 (write1 (write0 r))))))) +)\r:IO->IO +(\m:(IO->IO)->IO m + \r:IO write0 (write0 (write1 (write0 (write0 (write1 (write1 (write0 r))))))) +)\d:IO->IO +(\m:(IO->IO)->IO m + \r:IO write1 (write0 (write0 (write0 (write0 (write1 (write0 (write0 r))))))) +)\excl:IO->IO +(\m:(IO->IO)->IO m + \r:IO write0 (write1 (write0 (write1 (write0 (write0 (write0 (write0 r))))))) +)\lf:IO->IO + +H (e (l (l (o (comma (space (w (o (r (l (d (excl (lf exit))))))))))))) diff --git a/examples/primes.sysf b/examples/primes.sysf new file mode 100644 index 0000000..3111890 --- /dev/null +++ b/examples/primes.sysf @@ -0,0 +1,129 @@ +; primes -- list the primes, slowly +; +; This program outputs the prime numbers, one per line. It uses a unary +; representation and is not particular optimised, making it very slow. + +; Copyright (C) 2026 Sebastian G. Kirmayer <gloria@gloria-mundi.eu> +; +; Permission to use, copy, modify, and/or distribute this software for any +; purpose with or without fee is hereby granted. +; +; 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. + +/\IO\fix:\/X((X->IO)->X->IO)->X->IO\read:IO->IO->IO->IO\write0:IO->IO\write1:IO->IO\exit:IO + +#Pair[a b] \/X (a->b->X)->X +(\m:(\/a\/b a->b->Pair[a b])->IO m + /\A/\B\a:A\b:B/\X\x:A->B->X x a b +)\pair:\/a\/b a->b->Pair[a b] + +#Triple[a b c] \/X (a->b->c->X)->X +(\m:(\/a\/b\/c a->b->c->Triple[a b c])->IO m + /\A/\B/\C\a:A\b:B\c:C/\X\x:A->B->C->X x a b c +)\triple:\/a\/b\/c a->b->c->Triple[a b c] + +#Nat \/X (X->X)->X->X +(\m:Nat->IO m + /\X\s:X->X\z:X z +)\zero:Nat +(\m:(Nat->Nat)->IO m + \n:Nat /\X\s:X->X\z:X n X s (s z) +)\succ:Nat->Nat +(\m:(Nat->Nat)->IO m + \n:Nat n Pair[Nat Nat] + (\p:Pair[Nat Nat] p Pair[Nat Nat] \a:Nat\b:Nat pair Nat Nat (succ a) a) + (pair Nat Nat zero zero) + Nat + \a:Nat\b:Nat b +)\pred:Nat->Nat + +(\m:(Nat->Nat->Pair[Nat Nat])->IO m + \n:Nat\m:Nat + n Triple[Nat Nat Nat] + (\t:Triple[Nat Nat Nat] + t Triple[Nat Nat Nat] \div:Nat \rem:Nat \irem:Nat + irem Triple[Nat Nat Nat] + (\_:Triple[Nat Nat Nat] + triple Nat Nat Nat div (succ rem) (pred irem)) + (triple Nat Nat Nat (succ div) zero (pred m))) + (triple Nat Nat Nat zero zero (pred m)) + Pair[Nat Nat] + \div:Nat \rem:Nat \irem:Nat pair Nat Nat div rem +)\divmod:Nat->Nat->Pair[Nat Nat] + +(\m:Nat->IO m + (succ (succ zero)) +)\2:Nat + +(\m:Nat->IO m + (succ (succ (succ (succ (succ (succ (succ (succ (succ (succ zero)))))))))) +)\10:Nat + +(\m:(Nat->IO->IO)->IO m + \n:Nat n IO->IO (\_:IO->IO write1) write0 +)\print_bit:Nat->IO->IO + +(\m:(Nat->IO->IO)->IO m + \n:Nat n Nat->IO->IO + (\rest:Nat->IO->IO\cur:Nat\then:IO cur IO + (\_:IO divmod cur 10 IO \div:Nat\mod:Nat + divmod mod 2 IO \mod2:Nat\b1:Nat + divmod mod2 2 IO \mod4:Nat\b2:Nat + divmod mod4 2 IO \b8:Nat\b4:Nat + rest div + (print_bit b1 + (print_bit b2 + (print_bit b4 + (print_bit b8 + (write1 (write1 (write0 (write0 then))))))))) + then) + (\_:Nat\then:IO then) + n +)\print:Nat->IO->IO + +(\m:(IO->IO)->IO m + \_:IO write0 (write1 (write0 (write1 (write0 (write0 (write0 (write0 _))))))) +)\newline:IO->IO + +#Bool \/X X->X->X + +(\m:Bool->IO m /\X \f:X \t:X f)\false:Bool +(\m:Bool->IO m /\X \f:X \t:X t)\true:Bool +(\m:(Bool->Bool->Bool)->IO m + \a:Bool\b:Bool a Bool a b +)\and:Bool->Bool->Bool +(\m:(Bool->Bool->Bool)->IO m + \a:Bool\b:Bool a Bool b a +)\or:Bool->Bool->Bool + +#Maybe[a] \/X (a->X)->X->X + +(\m:(\/a a->Maybe[a])->IO m + /\A\a:A /\X \j:A->X\n:X j a +)\just:\/a a->Maybe[a] +(\m:(\/a Maybe[a])->IO m + /\A /\X\j:A->X\n:X n +)\nothing:\/a Maybe[a] + +(\m:(Nat->Bool)->IO m + \n:Nat + pred (pred n) Maybe[Nat] + (\r:Maybe[Nat] r Maybe[Nat] + (\d:Nat divmod n d Maybe[Nat] + \div:Nat\mod:Nat mod Maybe[Nat] + (\_:Maybe[Nat] just Nat (succ d)) + (nothing Nat)) + r) + (just Nat 2) + Bool (\_:Nat true) false +)\is_prime:Nat->Bool + +fix Nat (\f:Nat->IO\n:Nat + (\_:IO is_prime n IO _ (print n (newline _))) (f (succ n))) 2 +; print (pred 10) (newline exit) diff --git a/examples/primes2.sysf b/examples/primes2.sysf new file mode 100644 index 0000000..a3b1003 --- /dev/null +++ b/examples/primes2.sysf @@ -0,0 +1,195 @@ +; primes2 -- list the primes, slightly faster +; +; This program outputs the prime numbers, one per line. It uses a binary +; representation, so it is a bit faster than primes. + +; Copyright (C) 2026 Sebastian G. Kirmayer <gloria@gloria-mundi.eu> +; +; Permission to use, copy, modify, and/or distribute this software for any +; purpose with or without fee is hereby granted. +; +; 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. + +/\IO\fix:\/X((X->IO)->X->IO)->X->IO\read:IO->IO->IO->IO\write0:IO->IO\write1:IO->IO\exit:IO + +#Pair[a b] \/X (a->b->X)->X +(\m:(\/a\/b a->b->Pair[a b])->IO m + /\A/\B\a:A\b:B/\X\x:A->B->X x a b +)\pair:\/a\/b a->b->Pair[a b] + +#Bool \/X X->X->X +(\m:Bool->IO m /\X \f:X \t:X f)\false:Bool +(\m:Bool->IO m /\X \f:X \t:X t)\true:Bool +(\m:(Bool->Bool->Bool)->IO m + \a:Bool\b:Bool a Bool a b +)\and:Bool->Bool->Bool +(\m:(Bool->Bool->Bool)->IO m + \a:Bool\b:Bool a Bool b a +)\or:Bool->Bool->Bool + +#Maybe[a] \/X (a->X)->X->X +(\m:(\/a a->Maybe[a])->IO m + /\A\a:A /\X \j:A->X\n:X j a +)\just:\/a a->Maybe[a] +(\m:(\/a Maybe[a])->IO m + /\A /\X\j:A->X\n:X n +)\nothing:\/a Maybe[a] +(\m:(\/a\/b (a->b)->Maybe[a]->Maybe[b])->IO m + /\A/\B \f:A->B \x:Maybe[A] x Maybe[B] (\a:A just B (f a)) (nothing B) +)\map_maybe:\/a\/b (a->b)->Maybe[a]->Maybe[b] + +#List[a] \/X (a->X->X)->X->X +(\m:(\/a List[a])->IO m + /\A /\X \c:A->X->X \n:X n +)\nil:\/a List[a] +(\m:(\/a a->List[a]->List[a])->IO m + /\A \hd:A \tl:List[A] /\X \c:A->X->X \n:X c hd (tl X c n) +)\cons:\/a a->List[a]->List[a] +(\m:(\/a List[a]->Maybe[Pair[a List[a]]])->IO m + /\A \l:List[A] l Maybe[Pair[A List[A]]] + (\hd:A\r:Maybe[Pair[A List[A]]] just Pair[A List[A]] (pair A List[A] hd + (r List[A] + (\p:Pair[A List[A]] p List[A] (\h:A\t:List[A] cons A h t)) + (nil A)))) + (nothing Pair[A List[A]]) +)\uncons:\/a List[a]->Maybe[Pair[a List[a]]] + +#Nat List[Bool] +(\m:Nat->IO m + (nil Bool) +)\zero:Nat +(\m:(Nat->Nat)->IO m + \n:Nat + n Pair[Nat Nat] + (\bit:Bool\r:Pair[Nat Nat] r Pair[Nat Nat] \x:Nat\y:Nat + pair Nat Nat + (cons Bool bit x) + (bit Nat (cons Bool true x) (cons Bool false y))) + (pair Nat Nat zero (cons Bool true zero)) + Nat \x:Nat\y:Nat y +)\succ:Nat->Nat +(\m:(Nat->Maybe[Nat])->IO m + \n:Nat + n Pair[Nat Maybe[Nat]] + (\bit:Bool\r:Pair[Nat Maybe[Nat]] r Pair[Nat Maybe[Nat]] + \x:Nat\y:Maybe[Nat] + pair Nat Maybe[Nat] + (cons Bool bit x) + (bit Maybe[Nat] + (map_maybe Nat Nat (cons Bool true) y) + (just Nat (cons Bool false x)))) + (pair Nat Maybe[Nat] zero (nothing Nat)) + Maybe[Nat] \x:Nat\y:Maybe[Nat] y +)\pred:Nat->Maybe[Nat] +(\m:(Nat->Nat)->IO m + \n:Nat pred n Nat (\x:Nat x) zero +)\pred_:Nat->Nat +(\m:(Nat->Pair[Bool Nat])->IO m + \n:Nat + uncons Bool n Pair[Bool Nat] + (\p:Pair[Bool Nat] p) + (pair Bool Nat false zero) +)\divmod2:Nat->Pair[Bool Nat] +(\m:(Nat->Bool)->IO m + \n:Nat n Bool (\b:Bool\r:Bool b Bool r false) true +)\is_zero:Nat->Bool + + +(\m:(Nat->Nat->Nat)->IO m + \n:Nat + n Nat->Nat + (\bit:Bool\r:Nat->Nat\m:Nat + divmod2 (bit Nat m (succ m)) Nat + \x:Bool\y:Nat cons Bool x (r y)) + (\m:Nat m) +)\add:Nat->Nat->Nat +(\m:(Nat->Nat->Maybe[Nat])->IO m + \n:Nat\m:Nat + m Nat->Maybe[Nat] + (\bit:Bool\r:Nat->Maybe[Nat]\n:Nat + bit Maybe[Nat] (just Nat n) (pred n) Maybe[Nat] + (\n:Nat divmod2 n Maybe[Nat] + \x:Bool\y:Nat map_maybe Nat Nat (cons Bool x) (r y)) + (nothing Nat)) + (\n:Nat just Nat n) + n +)\sub:Nat->Nat->Maybe[Nat] + +(\m:(Nat->Nat->Pair[Bool Nat])->IO m + \n:Nat\m:Nat + sub n m Pair[Bool Nat] + (\x:Nat pair Bool Nat true x) + (pair Bool Nat false n) +)\try_sub:Nat->Nat->Pair[Bool Nat] + +; NOTE: Division by m+1 +(\m:(Nat->Nat->Pair[Nat Nat])->IO m + \n:Nat\m:Nat + n Pair[Nat Nat] + (\bit:Bool\p:Pair[Nat Nat] p Pair[Nat Nat] \div:Nat\mod:Nat + try_sub (cons Bool bit mod) (succ m) Pair[Nat Nat] + \bit2:Bool\mod2:Nat pair Nat Nat (cons Bool bit2 div) mod2) + (pair Nat Nat zero zero) +)\divmod:Nat->Nat->Pair[Nat Nat] + +(\m:Nat->IO m + (cons Bool true (cons Bool false (cons Bool false (cons Bool true zero)))) +)\9:Nat +(\m:Nat->IO m + (cons Bool false (cons Bool true zero)) +)\2:Nat + +(\m:(Bool->IO->IO)->IO m + \b:Bool b IO->IO write0 write1 +)\write_bit:Bool->IO->IO + +(\m:(Nat->IO->IO)->IO m + \n:Nat n Nat->IO->IO + (\_:Bool\rest:Nat->IO->IO\cur:Nat\then:IO + is_zero cur IO ( + divmod cur 9 IO \div:Nat\mod1:Nat + divmod2 mod1 IO \b1:Bool\mod2:Nat + divmod2 mod2 IO \b2:Bool\mod4:Nat + divmod2 mod4 IO \b4:Bool\mod8:Nat + divmod2 mod8 IO \b8:Bool\_:Nat + rest div + (write_bit b1 + (write_bit b2 + (write_bit b4 + (write_bit b8 + (write1 (write1 (write0 (write0 then))))))))) + then) + (\_:Nat\then:IO then) + n +)\print:Nat->IO->IO + +(\m:(IO->IO)->IO m + \_:IO write0 (write1 (write0 (write1 (write0 (write0 (write0 (write0 _))))))) +)\newline:IO->IO + +(\m:(\/X Nat->(X->X)->X->X)->IO m + /\X \n:Nat n (X->X)->X->X + (\bit:Bool\rest:(X->X)->X->X\f:X->X\x:X + rest (\x:X f (f x)) (bit X x (f x))) + (\f:X->X\x:X x) +)\loop:\/X Nat->(X->X)->X->X + +(\m:(Nat->Bool)->IO m + \n:Nat + loop Maybe[Nat] (pred_ (pred_ n)) + (\v:Maybe[Nat] v Maybe[Nat] + (\m:Nat divmod n m Maybe[Nat] \div:Nat\mod:Nat + is_zero mod Maybe[Nat] (just Nat (succ m)) (nothing Nat)) + v) + (just Nat (succ zero)) + Bool (\_:Nat true) false +)\is_prime:Nat->Bool + +fix Nat (\f:Nat->IO\n:Nat + (\_:IO is_prime n IO _ (print n (newline _))) (f (succ n))) 2 @@ -0,0 +1,62 @@ +#!/bin/sh +# Copyright (C) 2026 Sebastian G. Kirmayer <gloria@gloria-mundi.eu> +# +# This file is part of sysf-i386. +# +# sysf-i386 is free software: you can redistribute it and/or modify it under +# the terms of the GNU General Public License as published by the Free +# Software Foundation, either version 3 of the License, or (at your option) +# any later version. +# +# sysf-i386 is distributed in the hope that it will be useful, but WITHOUT ANY +# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS +# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more +# details. +# +# You should have received a copy of the GNU General Public License along +# with sysf-i386. If not, see <https://www.gnu.org/licenses/>. +# + +SYSF_VERSION=0.1 + +set -e + +VAL_APP=-1 +VAL_ABS=-2 +VAL_FIX=-3 +VAL_READ=-4 +VAL_WRITE0=-5 +VAL_WRITE1=-6 +VAL_EXIT=-7 + +PARSE_STACK_SIZE=0x800 +TYPE_STACK_SIZE=$((PARSE_STACK_SIZE*16)) +MACROS_SIZE=0x1000 + +string() { +label $1 + ascii "$2" +label $1_end +label $1_len $1 +} + +stderr() { +rodata +L stderr_string_start + ascii "$1" +L stderr_string_end +text + movl stderr_string_start^ %eax + movl stderr_string_end^ %ecx + call stderr +} + +prog() { + . ./start.asm + . ./parse.asm + . ./type.asm + . ./eval.asm + . ./string.asm +} + +. ./asm.sh diff --git a/parse.asm b/parse.asm new file mode 100644 index 0000000..1b23745 --- /dev/null +++ b/parse.asm @@ -0,0 +1,996 @@ +# Copyright (C) 2026 Sebastian G. Kirmayer <gloria@gloria-mundi.eu> +# +# This file is part of sysf-i386. +# +# sysf-i386 is free software: you can redistribute it and/or modify it under +# the terms of the GNU General Public License as published by the Free +# Software Foundation, either version 3 of the License, or (at your option) +# any later version. +# +# sysf-i386 is distributed in the hope that it will be useful, but WITHOUT ANY +# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS +# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more +# details. +# +# You should have received a copy of the GNU General Public License along +# with sysf-i386. If not, see <https://www.gnu.org/licenses/>. +# + +bss +align +label lineno + long 0 +label error_flag + long 0 +label macro_flag + long 0 + +label parse_stack_top + skip $((PARSE_STACK_SIZE*4)) +label parse_stack_bottom +label macro_types_start + skip $((MACROS_SIZE*4)) +label macro_types_end +label macro_start + skip $((PARSE_STACK_SIZE*16)) +label macro_end +label input + long 0 +label input_end + long 0 +data +align +label parse_stack_ptr + long parse_stack_bottom +label macro_type_ptr + long macro_types_start +label macro_ptr + long macro_start +text + +# STK +# { IDENT START, IDENT END } (if STK & STK_HAVE_IDENT) +# LINENO (if STK & STK_HAVE_LINENO) + +# On the type stack: +# callee type (if STK & STK_HAVE_VALUE) +# argument type (if STK & STK_SMALL_LAMBDA) + +# stack control words: +STK_BOTTOM=1 +STK_PAREN=2 +STK_SMALL_LAMBDA=4 +STK_BIG_LAMBDA=8 + +STK_TYPE_BOTTOM=256 +STK_TYPE_ARROW=512 +STK_TYPE_PAREN=1024 +STK_TYPE_FORALL=2048 + +STK_HAVE_VALUE=16 +STK_HAVE_IDENT=$((STK_SMALL_LAMBDA|STK_BIG_LAMBDA|STK_TYPE_FORALL)) +STK_HAVE_LINENO=$((STK_PAREN|STK_TYPE_PAREN)) + +BACKSLASH=0x5C +SLASH=0x2F +LPAREN=0x28 +RPAREN=0x29 +LBRACKET=0x5B +RBRACKET=0x5D +COLON=0x3A +SEMICOLON=0x3B +OCTOTHORPE=0x23 +SPACE=0x20 +TAB=0x09 +NEWLINE=0x0A +HYPHEN=0x2D +GREATER=0x3E +UNDERSCORE=0x5F + +label parse_push # (val: i32) -> () + movl @parse_stack_ptr %ecx + cmpl parse_stack_top %ecx + je overflow. + subl 4 %ecx + movl %eax @%ecx + movl %ecx @parse_stack_ptr + ret + +label parse_peek # () -> (val: i32) + movl @parse_stack_ptr %eax + movl @%eax %eax + ret + +label parse_pop # () -> (val: i32) + movl @parse_stack_ptr %eax + addl 4 @parse_stack_ptr + movl @%eax %eax + ret + +L overflow + movl msg_parse_overflow %eax + movl msg_parse_overflow_end %ecx + call report_error + jmp error +rodata +string msg_parse_overflow "Parse stack overflow +" +text + +label parse # (start: *i8, end: *i8) -> (term: *term) + pushl %ebx + pushl %edi + pushl %esi + pushl %ebp + movl %eax @input + movl %ecx @input_end + call align_heap + movl $STK_BOTTOM %eax + call parse_push + # push two bottoms -- this simplifies handling of unmatched ) + movl $STK_BOTTOM %eax + call parse_push + # push an extra poison to the type stack + call ty_poison + movl 0 @lineno + movl 0 @error_flag # this must occur after the ty_poison above +L loop + call skip_white + movl @input %eax + cmpl @input_end %eax + je eof. + cmpb $RPAREN @%eax + je right_paren. + call parse_peek + testl $STK_HAVE_VALUE %eax + jz parse_value. + call ty_top_is_forall + jne parse_value. + call parse_type + call ty_apply_forall + jmp loop^ + +L parse_value + movl @input %eax + movb @%eax %al + cmpb $BACKSLASH %al + je small_lambda. + cmpb $SLASH %al + je big_lambda. + cmpb $LPAREN %al + je left_paren. + # Variable terms + call read_ident + movl $STK_SMALL_LAMBDA %edx + call find_ident + movl %eax %esi + movl %ecx %ebp + movl %edx %edi + movl @heap_ptr %ecx + call push_value + testl %esi %esi + js bad_ident. + movl %edi %eax + movl %ebp %ecx + call ty_copy + jmp value_done. +L bad_ident + movl %esp %eax + call ty_poison +L value_done + movl %esp %eax + call apply + jmp loop^ + +L small_lambda + incl @input + call skip_white + call read_ident + movl %eax %esi + movl %ecx %eax + call parse_push + movl %esi %eax + call parse_push + movl $STK_SMALL_LAMBDA %eax + call parse_push + call skip_white + movl @input %eax + cmpl @input_end %eax + je no_colon. + movb @%eax %al + cmpb $COLON %al + jne no_colon. + incl @input + call parse_type + jmp loop^ + +L no_colon + call stderr_lineno + stderr "Missing argument type in lambda abstraction +" + call ty_poison + movl 1 @error_flag + jmp loop^ + +L big_lambda + movl @input %eax + incl %eax + cmpl @input_end %eax + je bad_char + movb @%eax %al + cmpb $BACKSLASH %al + jne bad_char + addl 2 @input + call skip_white + call read_ident + movl %eax %ebx + movl %ecx %eax + call parse_push + movl %ebx %eax + call parse_push + movl $STK_BIG_LAMBDA %eax + call parse_push + jmp loop^ + +L left_paren + incl @input + movl @lineno %eax + call parse_push + movl $STK_PAREN %eax + call parse_push + jmp loop^ + +L right_paren + incl @input + movl $STK_PAREN %eax + call close_paren + jmp loop^ + +L eof + movl $STK_BOTTOM %eax + call close_paren + popl %ebp + popl %esi + popl %edi + popl %ebx + movl @error_flag %eax + testl %eax %eax + jnz error + ret + +label close_paren # (type: i32) -> () + pushl %ebx + pushl %edi + pushl %ebp + movl %eax %ebx + # %ebx -- type wanted + call parse_pop + movl %eax %edi + # %edi -- type on stack + testl $STK_HAVE_VALUE %edi + jz no_value. +L have_value + testl $STK_HAVE_IDENT %edi + jz skip. + call parse_pop + call parse_pop +L skip + testl $STK_SMALL_LAMBDA %edi + jnz small_lambda. + testl $STK_BIG_LAMBDA %edi + jz skip. +L big_lambda + call ty_forall + jmp skip. +L small_lambda + call ty_arrow + movl @heap_ptr %ecx + movl @%ecx+-8 %ecx + movl $VAL_ABS %eax + call push_value +L skip + testl $STK_HAVE_LINENO %edi + jz no_lineno. + call parse_pop + movl %eax %ebp + # %ebp -- lineno +L no_lineno + call apply + testl %ebx %edi + jnz end. + testl $STK_BOTTOM %edi + jnz unmatched_right. + testl $STK_PAREN %edi + jnz unmatched_left. +L continue + call parse_pop + movl %eax %edi + jmp have_value^ # must have value since we just called apply + +L end + popl %ebp + popl %edi + popl %ebx + ret + +L unmatched_right + movl 1 @error_flag + call stderr_lineno + stderr "Unmatched ')' +" + call parse_pop + movl $STK_BOTTOM %eax + call parse_push + movl $((STK_BOTTOM|STK_HAVE_VALUE)) %eax + call parse_push + jmp end^ + +L unmatched_left + movl 1 @error_flag + xchgl %ebp @lineno + call stderr_lineno + movl %ebp @lineno + stderr "Unmatched '(' +" + jmp continue^ + +L no_value + # Push a poison value so we can continue + orl $STK_HAVE_VALUE %edi + movl 1 @error_flag + movl @heap_ptr %ecx + call push_value + call ty_poison + call stderr_lineno + # %edi -- parse stack element + testl $STK_PAREN %edi + jnz paren. + testl $STK_SMALL_LAMBDA %edi + jnz small. + testl $STK_BIG_LAMBDA %edi + jnz big. + testl $STK_BOTTOM %edi + jnz bottom. + ud2 +L paren + stderr "Empty parentheses +" + jmp have_value^ +L small + stderr "Empty lambda abstraction +" + jmp have_value^ +L big + stderr "Empty type lambda abstraction +" + jmp have_value^ +L bottom + stderr "Empty program +" + jmp have_value^ + +# We have just pushed a value. Check if it is an argument, and push the +# application if so. +label apply # () -> () + call parse_peek + testl $STK_HAVE_VALUE %eax + jnz do_apply. + call parse_pop + orl $STK_HAVE_VALUE %eax + call parse_push + ret +L do_apply + call ty_apply + movl @heap_ptr %ecx + movl @%ecx+-8 %ecx + movl @%ecx+-8 %ecx + movl $VAL_APP %eax + call push_value + ret + +label parse_type # () -> () + pushl %ebx + pushl %edi + pushl %esi + movl $STK_TYPE_BOTTOM %eax + call parse_push +L loop + call skip_white + movl @input %eax + cmpl @input_end %eax + je bad_eof + movb @%eax %al + cmpb $BACKSLASH %al + je forall. + cmpb $LPAREN %al + je left_paren. + # Variable + call read_ident + movl %eax %edi + movl %ecx %esi + # %edi..%esi -- ident + movl @macro_ptr %ebx + # %ebx -- macro iterator +L find_macro + cmpl macro_start %ebx + je no_macro. + subl 16 %ebx + movl %edi %eax + movl %esi %ecx + movl @%ebx %edx + pushl @%ebx+4 + call streq + je found_macro. + jmp find_macro^ + +L found_macro + movl @%ebx+12 %eax + movl @%ebx+8 %ebx + call ty_copy + # %ebx -- remaining arguments + call skip_white + movl @input %eax + cmpl @input_end %eax + je no_args. + cmpb $LBRACKET @%eax + jne no_args. + incl @input +L next_arg + call parse_type + decl %ebx + js extra_arg. + call ty_apply_forall +L arg_done + call skip_white + movl @input %eax + cmpl @input_end %eax + je bad_eof + cmpb $RBRACKET @%eax + jne next_arg^ + + incl @input +L no_args + testl %ebx %ebx + jg missing_args. + jl extra_args. +L have_args + jmp op. + +L extra_arg + call ty_pop + jmp arg_done^ + +L extra_args +rodata +string msg_extra_arg "Extraneous macro arguments +" +text + movl msg_extra_arg %eax + movl msg_extra_arg_end %ecx + call report_error + movl 1 @error_flag + jmp have_args^ + +L missing_args +rodata +string msg_missing_args "Missing macro arguments +" +text + movl msg_missing_args %eax + movl msg_missing_args_end %ecx + call report_error + movl 1 @error_flag +L fake_args + call ty_poison + call ty_apply_forall + decl %ebx %ebx + jnz fake_args^ + jmp have_args^ + +L no_macro + movl %edi %eax + movl %esi %ecx + movl $((STK_BIG_LAMBDA|STK_TYPE_FORALL)) %edx + call find_ident + testl %eax %eax + js not_found. + movl %ecx %eax + call ty_push + jmp op. +L not_found + call ty_poison + jmp op. + +L forall + movl @input %eax + incl %eax + cmpl @input_end %eax + je bad_eof + addl 2 @input + movb @%eax %al + cmpb $SLASH %al + jne bad_char + call skip_white + call read_ident + movl %eax %ebx + movl %ecx %eax + call parse_push + movl %ebx %eax + call parse_push + movl $STK_TYPE_FORALL %eax + call parse_push + jmp loop^ + +L left_paren + incl @input + movl @lineno %eax + call parse_push + movl $STK_TYPE_PAREN %eax + call parse_push + jmp loop^ + +L op + call skip_white + movl @input %eax + cmpl @input_end %eax + je end. + movb @%eax %al + cmpb $HYPHEN %al + je arrow. + cmpb $RPAREN %al + je right_paren. + jmp end. + +L arrow + movl @input %eax + incl %eax + cmpl @input_end %eax + je end. + movb @%eax %al + cmpb $GREATER %al + jne end. + addl 2 @input + movl $STK_TYPE_ARROW %eax + call parse_push + jmp loop^ + +L right_paren + movl $((STK_TYPE_PAREN|STK_TYPE_BOTTOM)) %eax + call close_type_paren + testl $STK_TYPE_PAREN %eax + jz done. + incl @input + jmp op^ + +L end + movl $STK_TYPE_BOTTOM %eax + call close_type_paren +L done + popl %esi + popl %edi + popl %ebx + ret + +label close_type_paren # (types: i32) -> (type: i32) + pushl %ebx + pushl %edi + pushl %esi + movl %eax %ebx + # %ebx -- wanted types +L loop + call parse_pop + movl %eax %edi + # %edi -- current type + testl $STK_HAVE_IDENT %edi + jz no_ident. + call parse_pop + call parse_pop +L no_ident + testl $STK_HAVE_LINENO %edi + jz no_lineno. + call parse_pop + movl %eax %esi + # %esi -- lineno +L no_lineno + testl %ebx %edi + jnz done. + testl $STK_TYPE_ARROW %edi + jnz arrow. + testl $STK_TYPE_PAREN %edi + jnz paren. + testl $STK_TYPE_FORALL %edi + jnz forall. + ud2 + +L arrow + call ty_arrow + jmp loop^ + +L paren + movl 1 @error_flag + xchgl %esi @lineno + call stderr_lineno + movl %esi @lineno + stderr "Unmatched '(' +" + jmp loop^ + +L forall + call ty_forall + jmp loop^ + +L done + movl %edi %eax + popl %esi + popl %edi + popl %ebx + ret + +label find_ident # (start: *i8, end: *i8, type: i32) -> (vidx: i32, tidx: i32, type: *type) + pushl %ebx + pushl %esi + pushl %edi + pushl %ebp + movl %edx %ebx + pushl 0 + pushl 0 + pushl %ecx + pushl %eax + call ty_top + movl %eax %edi + movl @parse_stack_ptr %esi + # %ebx -- type + # @%esp -- ident + # @%esp+4 -- ident end + # @%esp+8 -- value index + # @%esp+12 -- type index + # %esi -- pointer running down the stack + # %edi -- type stack pointer +L loop + # %ebp -- type & flags + movl @%esi %ebp + addl 4 %esi + testl $STK_HAVE_VALUE %ebp + jz no_value. + movl %edi %eax + call ty_skip + movl %eax %edi +L no_value + testl $STK_HAVE_IDENT %ebp + jz no_ident. + movl @%esi %eax + movl @%esi+4 %ecx + addl 8 %esi + movl @%esp %edx + pushl @%esp+4 + call streq + je found. +L no_ident + testl $STK_SMALL_LAMBDA %ebp + jz no_type. + movl %edi %eax + call ty_skip + movl %eax %edi +L no_type + leal @%esi+4 %eax + testl $STK_HAVE_LINENO %ebp + cmovnz %eax %esi + testl $((STK_BIG_LAMBDA|STK_TYPE_FORALL)) %ebp + jz no_type_inc. + incl @%esp+12 +L no_type_inc + testl $STK_SMALL_LAMBDA %ebp + jz no_value_inc. + incl @%esp+8 +L no_value_inc + testl $STK_BOTTOM %ebp + jz loop^ + movl @%esp %eax + movl @%esp+4 %ecx + call missing_ident +L error + movl -1 %eax + movl 1 @error_flag + jmp end. +L found + testl %ebx %ebp + jz bad_ident. + movl @%esp+8 %eax + movl @%esp+12 %ecx + movl %edi %edx +L end + addl 16 %esp + popl %ebp + popl %edi + popl %esi + popl %ebx + ret + +L bad_ident + movl @%esp %eax + movl @%esp+4 %ecx + movl %ebx %edx + call bad_ident + jmp error^ + +label read_ident # () -> (start: *i8, end: *i8) + movl @input %eax + movl %eax %ecx +L loop + cmpl @input_end %ecx + je done. + movb @%ecx %dl + incl %ecx + cmpb $UNDERSCORE %dl + je loop^ + cmpb 0x30 %dl + jb done_ungetc. + cmpb 0x39 %dl + jbe loop^ + cmpb 0x41 %dl + jb done_ungetc. + cmpb 0x5A %dl + jbe loop^ + cmpb 0x61 %dl + jb done_ungetc. + cmpb 0x7A %dl + jbe loop^ +L done_ungetc + decl %ecx +L done + cmpl %eax %ecx + je bad_char + movl %ecx @input + ret + +label bad_char + movl msg_bad_char %eax + movl msg_bad_char_end %ecx + call report_error + jmp error + +label bad_eof + cmpl 0 @macro_flag + jnz macro. + movl msg_bad_eof %eax + movl msg_bad_eof_end %ecx + call report_error + jmp error +L macro + movl msg_bad_eof_macro %eax + movl msg_bad_eof_macro_end %ecx + call report_error + jmp error + +rodata +string msg_bad_char "Unexpected character +" +string msg_bad_eof "Unexpected end of file +" +string msg_bad_eof_macro "Unexpected end of line +" +text + +# Skip whitespace including comments and macros. +label skip_white + movl @input %edx + xorl %ecx %ecx + cmpl %ecx @lineno + jne loop. + incl @lineno + incl %ecx +L loop + cmpl @input_end %edx + je done. + movb @%edx %al + cmpb $SPACE %al + je white. + cmpb $NEWLINE %al + je newline. + cmpb $TAB %al + je white. + cmpb $SEMICOLON %al + je comment. + cmpb $OCTOTHORPE %al + je macro. +L done + movl %edx @input + ret +L comment + incl %edx + cmpl @input_end %edx + je done^ + cmpb $NEWLINE @%edx + jne comment^ +L newline + incl @lineno + movl 1 %ecx + incl %edx + jmp loop^ +L white + xorl %ecx %ecx + incl %edx + jmp loop^ +L macro + testl %ecx %ecx + jz done^ + + pushl %ebx + pushl %edi + + # Macro handlings. + # 1. Find end of line + incl %edx + movl %edx @input +L loop + cmpl @input_end %edx + je eol. + cmpb $NEWLINE @%edx + je eol. + incl %edx + jmp loop^ +L eol + pushl @input_end + movl %edx @input_end + movl 1 @macro_flag + # Now, the entire input is just this line. So we can use normal parse + # functions to parse the line. There is no risk of infinite recursion since + # the input consists of a single line, so there are no newlines. + movl $STK_BOTTOM %eax + call parse_push + + call read_ident + movl @macro_ptr %edx + cmpl macro_end %edx + je macro_overflow. + movl %eax @%edx + movl %ecx @%edx+4 + movl @input %eax + cmpl @input_end %eax + je bad_eof + cmpb $LBRACKET @%eax + jne no_args. + incl @input + call skip_white +L loop + call read_ident + movl %eax %ebx + movl %ecx %eax + call parse_push + movl %ebx %eax + call parse_push + movl $STK_BIG_LAMBDA %eax + call parse_push + call skip_white + movl @input %eax + cmpl @input_end %eax + je bad_eof + cmpb $RBRACKET @%eax + jne loop^ + incl @input +L no_args + call parse_type + movl @input %eax + cmpl @input_end %eax + je ok. +rodata +string msg_macro_extra "Extraneous input at end of macro +" +text + movl msg_macro_extra %eax + movl msg_macro_extra_end %ecx + call report_error + movl 1 @error_flag + +L ok + xorl %edi %edi + # %edi -- num args +L loop + call parse_pop + testl $STK_BOTTOM %eax + jnz done. + incl %edi + call parse_pop + call parse_pop + call ty_forall + jmp loop^ +L done + movl @macro_ptr %eax + movl %edi @%eax+8 + movl @macro_type_ptr %edi + movl %edi @%eax+12 + call ty_top + movl %eax %ebx + call ty_skip + leal @%edi+%eax %ecx + subl %ebx %ecx + cmpl macro_types_end %ecx + ja macro_overflow. + movl %ecx @macro_type_ptr + # %ebx -- src + # %eax -- src end + # %edi -- dst + # %ecx -- dst end +L loop + movl @%ebx %edx + movl %edx @%edi + addl 4 %ebx + addl 4 %edi + cmpl %eax %ebx + jne loop^ + + call ty_pop + addl 16 @macro_ptr + movl @input_end %eax + movl %eax @input + popl @input_end + movl 0 @macro_flag + popl %edi + popl %ebx + jmp skip_white + +L macro_overflow + movl msg_macro_overflow %eax + movl msg_macro_overflow_end %ecx + call report_error + jmp error +rodata +string msg_macro_overflow "Too many macros +" +text + +label push_value # (val: i32, start ptr: *i32) + movl @heap_ptr %edx + addl 8 %edx + movl %edx @heap_ptr + cmpl @heap_end %edx + ja alloc. +L have_space + movl %eax @%edx+-4 + movl %ecx @%edx+-8 + ret +L alloc + pushl %eax + pushl %ecx + call alloc + popl %ecx + popl %eax + movl @heap_ptr %edx + jmp have_space^ + +label missing_ident # (start: *i8, end: *i8) -> () + pushl %eax + pushl %ecx + call stderr_lineno + stderr "Name not found: " + popl %ecx + popl %eax + call stderr + stderr " +" + ret + +label bad_ident # (start: *i8, end: *i8, wanted-type: i32) + pushl %edx + pushl %eax + pushl %ecx + call stderr_lineno + popl %ecx + popl %eax + call stderr + stderr " is not a " + popl %eax + call stderr_type + stderr " +" + ret + +label stderr_type # (type: i32) + testl $STK_SMALL_LAMBDA %eax + jnz small. +L big + stderr "type variable" + ret +L small + stderr "term variable" + ret diff --git a/start.asm b/start.asm new file mode 100644 index 0000000..b2bef32 --- /dev/null +++ b/start.asm @@ -0,0 +1,456 @@ +# Copyright (C) 2026 Sebastian G. Kirmayer <gloria@gloria-mundi.eu> +# +# This file is part of sysf-i386. +# +# sysf-i386 is free software: you can redistribute it and/or modify it under +# the terms of the GNU General Public License as published by the Free +# Software Foundation, either version 3 of the License, or (at your option) +# any later version. +# +# sysf-i386 is distributed in the hope that it will be useful, but WITHOUT ANY +# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS +# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more +# details. +# +# You should have received a copy of the GNU General Public License along +# with sysf-i386. If not, see <https://www.gnu.org/licenses/>. +# + +# Syscall numbers +NR_exit=1 +NR_read=3 +NR_write=4 +NR_open=5 +NR_close=6 +NR_brk=45 + +text +label _start + call init_heap + + # option parsing + leal @%esp+4 %ebp + +L loop + addl 4 %ebp + movl @%ebp %ebx + testl %ebx %ebx + jz done. + movb @%ebx %cl + cmpb 0x2D %cl # - + jne filename. + incl %ebx + movb @%ebx %cl + cmpb 0x00 %cl + je filename. + cmpb 0x2D %cl # - + je longopt. + cmpb 0x3F %cl # ? + je usage + cmpb 0x56 %cl # V + je print_version + jmp bad_usage + +L longopt + incl %ebx + movb @%ebx %cl + cmpb 0x00 %cl + je opts_end. + movl %ebx %eax + call strnul + pushl %eax + pushl %eax + movl flag_version %eax + movl flag_version_end %ecx + movl %ebx %edx + call streq + je print_version + movl flag_help %eax + movl flag_help_end %ecx + movl %ebx %edx + call streq + je usage + jmp bad_usage + +L opts_end + addl 4 %ebp + movl @%ebp %ebx + testl %ebx %ebx + jz done. +L filename + movl @%ebp+4 %eax + testl %eax %eax + jnz bad_usage + movl @%ebp %ebx + movb @%ebx %cl + cmpb 0x2D %cl + jne open_file. + movb @%ebx %cl + cmpb 0x00 %cl + je done. +L open_file + movl $NR_open %eax + xorl %ecx %ecx + int 0x80 + testl %eax %eax + js open_failed. + movl %eax %edi + movl @heap_ptr %esi + call slurp + movl %edi %ebx + movl $NR_close %eax + int 0x80 + movl %esi %ebx + jmp slurped. + +L open_failed + stderr 'Failed to open ' + movl %ebx %eax + call strnul + movl %eax %ecx + movl %ebx %eax + call stderr + stderr ' +' + jmp error + +L done + # slurp(stdin) + xorl %eax %eax + movl @heap_ptr %ebx + call slurp +L slurped + # parse(slurped code) + movl %ebx %eax + movl @heap_ptr %ecx + call parse + call ty_top + movl %eax %ebx + call ty_main + call ty_top + movl %ebx %ecx + call ty_eq + jne bad_main. + movl @heap_ptr %eax + jmp execute + +L bad_main + stderr 'Bad main type: ' + movl %ebx %eax + call ty_stderr + stderr ' +' + jmp error + +label ty_main + # fix + movl 0 %eax + call ty_var + movl 1 %eax + call ty_var + call ty_arrow + movl 0 %eax + call ty_var + movl 1 %eax + call ty_var + call ty_arrow + call ty_arrow + movl 0 %eax + call ty_var + movl 1 %eax + call ty_var + call ty_arrow + call ty_arrow + call ty_forall + # read + movl 0 %eax + call ty_var + movl 0 %eax + call ty_var + movl 0 %eax + call ty_var + movl 0 %eax + call ty_var + call ty_arrow + call ty_arrow + call ty_arrow + # write0 + movl 0 %eax + call ty_var + movl 0 %eax + call ty_var + call ty_arrow + # write1 + movl 0 %eax + call ty_var + movl 0 %eax + call ty_var + call ty_arrow + # exit + movl 0 %eax + call ty_var + movl 0 %eax + call ty_var + call ty_arrow + call ty_arrow + call ty_arrow + call ty_arrow + call ty_arrow + call ty_forall + ret + +label slurp # (fd: i32) -> () + pushl %ebx + movl %eax %ebx + # %ebx: file descriptor +L start + movl @heap_ptr %ecx + movl @heap_end %edx +L loop + subl %ecx %edx + jz alloc. + movl $NR_read %eax + int 0x80 + addl %ecx %edx + testl %eax %eax + js fail. + jz done. + addl %eax %ecx + jmp loop^ +L alloc + movl %ecx @heap_ptr + call alloc + jmp start^ +L done + movl %ecx @heap_ptr + popl %ebx + ret +L fail + stderr 'Failed to read program +' + jmp error + +bss +align +label heap_ptr + long 0 +label heap_end + long 0 + +text +label init_heap # () -> () + movl %ebx %ecx + xorl %ebx %ebx + movl $NR_brk %eax + int 0x80 + movl %eax @heap_ptr + movl %eax @heap_end + movl %ecx %ebx + ret + +label align_heap # () -> () + movl @heap_ptr %eax + addl 3 %eax + andl $((~3)) %eax + movl %eax @heap_ptr + ret + +label alloc # () -> () + movl %ebx %ecx + movl @heap_end %ebx + addl 0x1000 %ebx + movl $NR_brk %eax + int 0x80 + cmpl %eax %ebx + jne error + movl %eax @heap_end + movl %ecx %ebx + ret + +bss +label buffer_start + skip 0x100 +label buffer_cap buffer_start +align +label buffer_pos + long 0 +label buffer_len + long 0 +text + +# -1: EOF +# 0: 0 +# 1: 1 +label read # () -> (bit: i32) + movl @buffer_pos %ecx + movl %ecx %edx + shrl 3 %edx + cmpl @buffer_len %edx + je read. + xorl %eax %eax + movb @buffer_start+%edx %al + andl 7 %ecx + shrl %cl %eax + andl 1 %eax + incl @buffer_pos + ret + +L read + pushl %ebx + xorl %ebx %ebx + movl buffer_start %ecx + movl buffer_cap %edx + movl $NR_read %eax + int 0x80 + popl %ebx + testl %eax %eax + js error. + jz eof. + movl %eax @buffer_len + movl 0 @buffer_pos + jmp read + +L eof + movl -1 %eax + ret + +L error + stderr 'Error reading from stdin +' + jmp error + +bss +label write_buf + byte 0 +label write_bit + byte 0 +text + +label write0 + movl 0 %eax + jmp write. +label write1 + movl 1 %eax +L write + xorl %ecx %ecx + movb @write_bit %cl + shll %cl %eax + orb %al @write_buf + incb %cl + cmpb 8 %cl + je do_write. + movb %cl @write_bit + ret +L do_write + movb 0 @write_bit + pushl %ebx + movl 1 %ebx + movl write_buf %ecx + movl 1 %edx + movl $NR_write %eax + int 0x80 + popl %ebx + movb 0 @write_buf + ret + +label exit + movl $NR_exit %eax + xorl %ebx %ebx + int 0x80 + +label usage + call print_usage + jmp exit + +label bad_usage + call print_usage + jmp error + +label print_usage + movl 1 %ebx + movl usage_info %ecx + movl usage_info_len %edx + movl $NR_write %eax + int 0x80 + ret + +label print_version + movl 1 %ebx + movl version_info %ecx + movl version_info_len %edx + movl $NR_write %eax + int 0x80 + jmp exit + +label error + movl $NR_exit %eax + movl 1 %ebx + int 0x80 + +label stderr + pushl %ebx + movl %ecx %edx + movl %eax %ecx + subl %eax %edx + movl 2 %ebx + movl $NR_write %eax + int 0x80 + popl %ebx + ret + +label stderr_lineno + pushl %ebx + pushl %ebp + movl %esp %ebp + movl %esp %ebx + subl 0x20 %esp + subl 2 %ebx + movb 0x3A @%ebx + movb 0x20 @%ebx+1 + movl @lineno %eax + movl 10 %ecx +L loop + xorl %edx %edx + divl %ecx + addl 0x30 %edx + decl %ebx + movb %dl @%ebx + testl %eax %eax + jnz loop^ + subl 5 %ebx + movb 0x4C @%ebx + movb 0x69 @%ebx+1 + movb 0x6E @%ebx+2 + movb 0x65 @%ebx+3 + movb 0x20 @%ebx+4 + movl %ebx %eax + movl %ebp %ecx + call stderr + movl %ebp %esp + popl %ebp + popl %ebx + ret + +label report_error + pushl %eax + pushl %ecx + call stderr_lineno + popl %ecx + popl %eax + call stderr + ret + +rodata +string flag_version "version" +string flag_help "help" + +string version_info "\ +sysf-i386 $SYSF_VERSION +Copyright (C) 2026 Sebastian G. Kirmayer, GNU GPLv3+ +" + +string usage_info "\ +Usage: + sysf FILENAME + sysf --version +" diff --git a/string.asm b/string.asm new file mode 100644 index 0000000..4bf67d7 --- /dev/null +++ b/string.asm @@ -0,0 +1,40 @@ +# Copyright (C) 2026 Sebastian G. Kirmayer <gloria@gloria-mundi.eu> +# +# This file is part of sysf-i386. +# +# sysf-i386 is free software: you can redistribute it and/or modify it under +# the terms of the GNU General Public License as published by the Free +# Software Foundation, either version 3 of the License, or (at your option) +# any later version. +# +# sysf-i386 is distributed in the hope that it will be useful, but WITHOUT ANY +# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS +# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more +# details. +# +# You should have received a copy of the GNU General Public License along +# with sysf-i386. If not, see <https://www.gnu.org/licenses/>. +# + +text +label strnul + movl %edi %edx + movl %eax %edi + xorl %eax %eax + movl -1 %ecx + repnz scasb + leal @%edi+-1 %eax + ret + +label streq + subl %eax %ecx + subl %edx @%esp+4 + cmpl %ecx @%esp+4 + jne end. + xchgl %eax %esi + xchgl %edx %edi + repz cmpsb + movl %eax %esi + movl %edx %edi +L end + ret 4 diff --git a/type.asm b/type.asm new file mode 100644 index 0000000..a866e74 --- /dev/null +++ b/type.asm @@ -0,0 +1,555 @@ +# Copyright (C) 2026 Sebastian G. Kirmayer <gloria@gloria-mundi.eu> +# +# This file is part of sysf-i386. +# +# sysf-i386 is free software: you can redistribute it and/or modify it under +# the terms of the GNU General Public License as published by the Free +# Software Foundation, either version 3 of the License, or (at your option) +# any later version. +# +# sysf-i386 is distributed in the hope that it will be useful, but WITHOUT ANY +# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS +# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more +# details. +# +# You should have received a copy of the GNU General Public License along +# with sysf-i386. If not, see <https://www.gnu.org/licenses/>. +# + +TY_POISON=-1 +TY_ARROW=-2 +TY_FORALL=-3 + +bss +align +label type_stack_top + skip $((TYPE_STACK_SIZE*4)) +label type_stack_bottom +label type_stack2 + skip $TYPE_STACK_SIZE +data +align +label type_stack_ptr + long type_stack_bottom +text + +label ty_push # (ty: i32) -> () + movl @type_stack_ptr %ecx + cmpl type_stack_top %ecx + je ty_overflow + subl 4 %ecx + movl %eax @%ecx + movl %ecx @type_stack_ptr + ret + +label ty_overflow + movl msg_type_stack_overflow %eax + movl msg_type_stack_overflow_end %ecx + call report_error + jmp error + +rodata +string msg_type_stack_overflow "Type stack overflow +" +text + +label ty_eq # (ty1: *type, ty2: *type) -> ZF + pushl %ebx + movl 1 %edx +L loop + decl %edx + + movl @%eax %ebx + cmpl @%ecx %ebx + jne diff. + + leal @%edx+2 %ebx + cmpl $TY_ARROW @%eax + cmove %ebx %edx + + leal @%edx+1 %ebx + cmpl $TY_FORALL @%eax + cmove %ebx %edx + + addl 4 %eax + addl 4 %ecx + testl %edx %edx + jnz loop^ +L done + popl %ebx + ret +L diff + cmpl $TY_POISON @%eax + je done^ + cmpl $TY_POISON @%ecx + jmp done^ + + +label ty_poison # () -> () + movl 1 @error_flag + movl $TY_POISON %eax + jmp ty_push + +label ty_apply # () -> () + movl @type_stack_ptr %eax + call ty_skip + cmpl $TY_ARROW @%eax + jne no_arrow. + + pushl %eax + addl 4 %eax + movl @type_stack_ptr %ecx + call ty_eq + popl %eax + jne loud_fail. + addl 4 %eax + call ty_skip + movl %eax @type_stack_ptr + ret + +L no_arrow + cmpl $TY_POISON @%eax + je silent_fail. +L loud_fail + pushl %eax + call stderr_lineno + stderr "Failed to apply " + movl @%esp %eax + call ty_stderr + stderr " to " + movl @type_stack_ptr %eax + call ty_stderr + stderr " +" + popl %eax +L silent_fail + call ty_skip + subl 4 %eax + movl %eax @type_stack_ptr + movl $TY_POISON @%eax + movl 1 @error_flag + ret + +label ty_apply_forall # () -> () + movl @type_stack_ptr %eax + call ty_skip + cmpl $TY_FORALL @%eax + jne no_forall. + + # 1. Determine the number of substitutions + pushl %eax + addl 4 %eax + xorl %ecx %ecx + xorl %edx %edx + call ty_subst + # @%esp -- start of forall + # %eax -- number of substitutions + + # 2. Allocate space, by moving the substituted type up the stack. + movl @%esp %ecx + subl @type_stack_ptr %ecx + subl 4 %ecx + mull %ecx + # %eax is size delta + movl @type_stack_ptr %ecx + negl %eax + addl %ecx %eax + # We will discard the outer forall. If there are no substitutions, this + # means the move below is broken since %ecx < %eax, but it doesn't matter + # since we will never substitute. + addl 4 %eax + cmpl type_stack_top %eax + jb ty_overflow + movl %eax @type_stack_ptr +L loop + movl @%ecx %edx + movl %edx @%eax + addl 4 %ecx + addl 4 %eax + cmpl @%esp %ecx + jne loop^ + + # 3. Perform the substitution + movl %eax %ecx + popl %eax + addl 4 %eax + movl @type_stack_ptr %edx + movl %ecx @type_stack_ptr + jmp ty_subst # tail call + +L no_forall + cmpl $TY_POISON @%eax + je silent_fail. + pushl %eax + call stderr_lineno + stderr "Failed to apply " + movl @%esp %eax + call ty_stderr + stderr " to a type +" + popl %eax +L silent_fail + call ty_skip + subl 4 %eax + movl %eax @type_stack_ptr + movl $TY_POISON @%eax + movl 1 @error_flag + ret + +# If out is 0, subst must also be 0. Then no substitution is performed, +# and subst count is returned. +label ty_subst # (in: *type, out: *type, subst: *type) -> ... + pushl %ebx + pushl %edi + pushl %esi + pushl %ebp + pushl %edx + movl %eax %ebx + movl type_stack2 %edi + xorl %ebp %ebp + movl %ecx %esi + # %ebx -- in ptr + # %edi -- stack2 ptr + # %ebp -- index offset + # %esi -- out ptr +L loop + movl @%ebx %eax + addl 4 %ebx + + cmpl $TY_ARROW %eax + je arrow. + cmpl $TY_FORALL %eax + je forall. + cmpl $TY_POISON %eax + je var. + + leal @%eax+-1 %ecx + cmpl %ebp %eax + je do_subst. + cmova %ecx %eax + +L var + testl %esi %esi + jz next. + movl %eax @%esi + addl 4 %esi +L next + cmpl type_stack2 %edi + je done. + decl %edi + cmpb 1 @%edi + je loop^ + cmpb 2 @%edi + je close_forall. + ud2 +L close_forall + decl %ebp + jmp next^ + +L do_subst + testl %esi %esi + jz no_copy. + + movl @%esp %eax + movl %esi %ecx + movl %ebp %edx + pushl %edi + call ty_copy2 + movl %eax %esi + jmp next^ + +L no_copy + incl @%esp + jmp next^ + +L arrow + testl %esi %esi + jz no_copy. + movl %eax @%esi + addl 4 %esi +L no_copy + movb 1 @%edi + incl %edi + jmp loop^ + +L forall + testl %esi %esi + jz no_copy. + movl %eax @%esi + addl 4 %esi +L no_copy + movl 2 @%edi + incl %edi + incl %ebp + jmp loop^ + +L done + popl %eax + popl %ebp + popl %esi + popl %edi + popl %ebx + ret + +label ty_stderr # (ty: *type) -> () + pushl %ebx + pushl %edi + pushl %ebp + movl %eax %ebx + movl type_stack2 %edi + movl 0 %ebp + # %ebx -- type ptr + # %edi -- stack2 ptr + # %ebp -- index offset +L loop + movl @%ebx %eax + addl 4 %ebx + + cmpl $TY_ARROW %eax + je arrow. + cmpl $TY_FORALL %eax + je forall. + cmpl $TY_POISON %eax + je poison. + + subl %ebp %eax + jae outside. + notl %eax + movl 0x61 %ecx + jmp baseconv. +L outside + movl 0x41 %ecx +L baseconv + call stderr_name +L next + cmpl type_stack2 %edi + je done. + decl %edi + cmpb 0 @%edi + je close_paren. + cmpb 1 @%edi + je close_arrow. + cmpb 2 @%edi + je close_forall. + ud2 +L close_paren + stderr ")" + jmp next^ +L close_arrow + stderr " -> " + jmp loop^ +L close_forall + decl %ebp + jmp next^ + +L done + popl %ebp + popl %edi + popl %ebx + ret + +L arrow + movb 1 @%edi + incl %edi + cmpl $TY_ARROW @%ebx + je paren. + cmpl $TY_FORALL @%ebx + jne loop^ +L paren + movb 0 @%edi + incl %edi + stderr "(" + jmp loop^ + +L forall + stderr "\\/" + movl 0x61 %ecx + movl %ebp %eax + incl %ebp + call stderr_name + stderr " " + movl 2 @%edi + incl %edi + jmp loop^ + +L poison + stderr "<error>" + jmp next^ + +label stderr_name # (name: i32, offset: i32) -> () + pushl %edi + pushl %ebx + movl %esp %ebx + subl 16 %esp + movl 26 %edi + incl %eax +L baseconv_loop + decl %eax + xorl %edx %edx + divl %edi + addl %ecx %edx + decl %ebx + movb %dl @%ebx + testl %eax %eax + jnz baseconv_loop^ + movl %ebx %eax + leal @%esp+16 %ecx + call stderr + addl 16 %esp + popl %ebx + popl %edi + ret + +label ty_top # () -> (top: *type) + movl @type_stack_ptr %eax + ret + +label ty_pop # () -> () + movl @type_stack_ptr %eax + call ty_skip + movl %eax @type_stack_ptr + ret + +label ty_skip # (ty: *type) -> (next: *type) + movl 1 %ecx +L loop + decl %ecx + + leal @%ecx+2 %edx + cmpl $TY_ARROW @%eax + cmove %edx %ecx + + leal @%ecx+1 %edx + cmpl $TY_FORALL @%eax + cmove %edx %ecx + + addl 4 %eax + testl %ecx %ecx + jnz loop^ + ret + +label ty_forall # () -> () + movl $TY_FORALL %eax + jmp ty_push + +label ty_var # (idx: i32) -> () + jmp ty_push + +label ty_arrow # () -> () + movl @type_stack_ptr %eax + call ty_skip + pushl %eax + movl %eax %ecx + movl @type_stack_ptr %eax + call reverse + movl @%esp %eax + call ty_skip + movl %eax %ecx + xchgl %eax @%esp + call reverse + movl @type_stack_ptr %eax + popl %ecx + call reverse + movl $TY_ARROW %eax + jmp ty_push + +label reverse # (start: *i32, end: *i32) -> () +L loop + cmpl %ecx %eax + je done. + subl 4 %ecx + cmpl %ecx %eax + je done. + movl @%eax %edx + xchgl @%ecx %edx + movl %edx @%eax + addl 4 %eax + jmp loop^ +L done + ret + +label ty_top_is_forall # () -> (ZF) + movl @type_stack_ptr %eax + cmpl $TY_FORALL @%eax + ret + +label ty_copy # (ty: *type, shift: i32) -> () + pushl %ecx + pushl %eax + call ty_skip + movl @%esp %ecx + subl %eax %ecx + addl @type_stack_ptr %ecx + cmpl type_stack_top %ecx + jb ty_overflow + movl %ecx @type_stack_ptr + popl %eax + popl %edx + pushl type_stack2 + call ty_copy2 + ret + +label ty_copy2 # (src: i32, dst: i32, shift: i32, stack2: i32) -> (dstend: i32) + pushl %ebx + pushl %edi + pushl %esi + movl @%esp+16 %edi + movb 0 @%edi + incl %edi + xorl %ebx %ebx + # %eax -- src ptr + # %ecx -- dst ptr + # %ebx -- index offset + # %edx -- index shift + # %edi -- stack2 ptr +L loop + movl @%eax %esi + addl 4 %eax + + cmpl $TY_ARROW %esi + je arrow. + cmpl $TY_FORALL %esi + je forall. + cmpl $TY_POISON %esi + je var. + + cmpl %ebx %esi + jb var. + addl %edx %esi +L var + movl %esi @%ecx + addl 4 %ecx +L next + decl %edi + cmpb 0 @%edi + je done. + cmpb 1 @%edi + je loop^ + cmpb 2 @%edi + je forall_done. + ud2 +L forall_done + decl %ebx + jmp next^ + +L arrow + movl %esi @%ecx + addl 4 %ecx + movb 1 @%edi + incl %edi + jmp loop^ + +L forall + movl %esi @%ecx + addl 4 %ecx + movb 2 @%edi + incl %edi + incl %ebx + jmp loop^ + +L done + movl %ecx %eax + popl %esi + popl %edi + popl %ebx + ret 4 |