Faster implementation of integer-to-ascii conversion. I think....

src/conversions.cc

Index: src/conversions.cc
===================================================================
--- src/conversions.cc	(revision 3813)
+++ src/conversions.cc	(working copy)
@@ -425,6 +425,252 @@
 }
 
 
+// Tables and constants for fast integer to ASCII conversion.
+// Contains the first 1000 integers in ASCII form.  Each integer starts with
+// a minus (-), which is skipped for positive numbers.
+static const int kIToATableStride = 4;
+static const char* kIToATable =
+  "-0..-1---2..-3..-4..-5..-6..-7..-8..-9.."
+  "-10.-11.-12.-13.-14.-15.-16.-17.-18.-19."
+  "-20.-21.-22.-23.-24.-25.-26.-27.-28.-29."
+  "-30.-31.-32.-33.-34.-35.-36.-37.-38.-39."
+  "-40.-41.-42.-43.-44.-45.-46.-47.-48.-49."
+  "-50.-51.-52.-53.-54.-55.-56.-57.-58.-59."
+  "-60.-61.-62.-63.-64.-65.-66.-67.-68.-69."
+  "-70.-71.-72.-73.-74.-75.-76.-77.-78.-79."
+  "-80.-81.-82.-83.-84.-85.-86.-87.-88.-89."
+  "-90.-91.-92.-93.-94.-95.-96.-97.-98.-99."
+  "-100-101-102-103-104-105-106-107-108-109"
+  "-110-111-112-113-114-115-116-117-118-119"
+  "-120-121-122-123-124-125-126-127-128-129"
+  "-130-131-132-133-134-135-136-137-138-139"
+  "-140-141-142-143-144-145-146-147-148-149"
+  "-150-151-152-153-154-155-156-157-158-159"
+  "-160-161-162-163-164-165-166-167-168-169"
+  "-170-171-172-173-174-175-176-177-178-179"
+  "-180-181-182-183-184-185-186-187-188-189"
+  "-190-191-192-193-194-195-196-197-198-199"
+  "-200-201-202-203-204-205-206-207-208-209"
+  "-210-211-212-213-214-215-216-217-218-219"
+  "-220-221-222-223-224-225-226-227-228-229"
+  "-230-231-232-233-234-235-236-237-238-239"
+  "-240-241-242-243-244-245-246-247-248-249"
+  "-250-251-252-253-254-255-256-257-258-259"
+  "-260-261-262-263-264-265-266-267-268-269"
+  "-270-271-272-273-274-275-276-277-278-279"
+  "-280-281-282-283-284-285-286-287-288-289"
+  "-290-291-292-293-294-295-296-297-298-299"
+  "-300-301-302-303-304-305-306-307-308-309"
+  "-310-311-312-313-314-315-316-317-318-319"
+  "-320-321-322-323-324-325-326-327-328-329"
+  "-330-331-332-333-334-335-336-337-338-339"
+  "-340-341-342-343-344-345-346-347-348-349"
+  "-350-351-352-353-354-355-356-357-358-359"
+  "-360-361-362-363-364-365-366-367-368-369"
+  "-370-371-372-373-374-375-376-377-378-379"
+  "-380-381-382-383-384-385-386-387-388-389"
+  "-390-391-392-393-394-395-396-397-398-399"
+  "-400-401-402-403-404-405-406-407-408-409"
+  "-410-411-412-413-414-415-416-417-418-419"
+  "-420-421-422-423-424-425-426-427-428-429"
+  "-430-431-432-433-434-435-436-437-438-439"
+  "-440-441-442-443-444-445-446-447-448-449"
+  "-450-451-452-453-454-455-456-457-458-459"
+  "-460-461-462-463-464-465-466-467-468-469"
+  "-470-471-472-473-474-475-476-477-478-479"
+  "-480-481-482-483-484-485-486-487-488-489"
+  "-490-491-492-493-494-495-496-497-498-499"
+  "-500-501-502-503-504-505-506-507-508-509"
+  "-510-511-512-513-514-515-516-517-518-519"
+  "-520-521-522-523-524-525-526-527-528-529"
+  "-530-531-532-533-534-535-536-537-538-539"
+  "-540-541-542-543-544-545-546-547-548-549"
+  "-550-551-552-553-554-555-556-557-558-559"
+  "-560-561-562-563-564-565-566-567-568-569"
+  "-570-571-572-573-574-575-576-577-578-579"
+  "-580-581-582-583-584-585-586-587-588-589"
+  "-590-591-592-593-594-595-596-597-598-599"
+  "-600-601-602-603-604-605-606-607-608-609"
+  "-610-611-612-613-614-615-616-617-618-619"
+  "-620-621-622-623-624-625-626-627-628-629"
+  "-630-631-632-633-634-635-636-637-638-639"
+  "-640-641-642-643-644-645-646-647-648-649"
+  "-650-651-652-653-654-655-656-657-658-659"
+  "-660-661-662-663-664-665-666-667-668-669"
+  "-670-671-672-673-674-675-676-677-678-679"
+  "-680-681-682-683-684-685-686-687-688-689"
+  "-690-691-692-693-694-695-696-697-698-699"
+  "-700-701-702-703-704-705-706-707-708-709"
+  "-710-711-712-713-714-715-716-717-718-719"
+  "-720-721-722-723-724-725-726-727-728-729"
+  "-730-731-732-733-734-735-736-737-738-739"
+  "-740-741-742-743-744-745-746-747-748-749"
+  "-750-751-752-753-754-755-756-757-758-759"
+  "-760-761-762-763-764-765-766-767-768-769"
+  "-770-771-772-773-774-775-776-777-778-779"
+  "-780-781-782-783-784-785-786-787-788-789"
+  "-790-791-792-793-794-795-796-797-798-799"
+  "-800-801-802-803-804-805-806-807-808-809"
+  "-810-811-812-813-814-815-816-817-818-819"
+  "-820-821-822-823-824-825-826-827-828-829"
+  "-830-831-832-833-834-835-836-837-838-839"
+  "-840-841-842-843-844-845-846-847-848-849"
+  "-850-851-852-853-854-855-856-857-858-859"
+  "-860-861-862-863-864-865-866-867-868-869"
+  "-870-871-872-873-874-875-876-877-878-879"
+  "-880-881-882-883-884-885-886-887-888-889"
+  "-890-891-892-893-894-895-896-897-898-899"
+  "-900-901-902-903-904-905-906-907-908-909"
+  "-910-911-912-913-914-915-916-917-918-919"
+  "-920-921-922-923-924-925-926-927-928-929"
+  "-930-931-932-933-934-935-936-937-938-939"
+  "-940-941-942-943-944-945-946-947-948-949"
+  "-950-951-952-953-954-955-956-957-958-959"
+  "-960-961-962-963-964-965-966-967-968-969"
+  "-970-971-972-973-974-975-976-977-978-979"
+  "-980-981-982-983-984-985-986-987-988-989"
+  "-990-991-992-993-994-995-996-997-998-999";
+
+
+// Table that maps i to the ASCII representation of i.  Only the
+// even numbers are in the table since the odd ones can be
+// branchlessly created from those.
+static const int kLeadingZerosIToATableStride = 3;
+static const char* kLeadingZerosIToATable =
+  "000002004006008010012014016018020022024026028030032034036038"
+  "040042044046048050052054056058060062064066068070072074076078"
+  "080082084086088090092094096098100102104106108110112114116118"
+  "120122124126128130132134136138140142144146148150152154156158"
+  "160162164166168170172174176178180182184186188190192194196198"
+  "200202204206208210212214216218220222224226228230232234236238"
+  "240242244246248250252254256258260262264266268270272274276278"
+  "280282284286288290292294296298300302304306308310312314316318"
+  "320322324326328330332334336338340342344346348350352354356358"
+  "360362364366368370372374376378380382384386388390392394396398"
+  "400402404406408410412414416418420422424426428430432434436438"
+  "440442444446448450452454456458460462464466468470472474476478"
+  "480482484486488490492494496498500502504506508510512514516518"
+  "520522524526528530532534536538540542544546548550552554556558"
+  "560562564566568570572574576578580582584586588590592594596598"
+  "600602604606608610612614616618620622624626628630632634636638"
+  "640642644646648650652654656658660662664666668670672674676678"
+  "680682684686688690692694696698700702704706708710712714716718"
+  "720722724726728730732734736738740742744746748750752754756758"
+  "760762764766768770772774776778780782784786788790792794796798"
+  "800802804806808810812814816818820822824826828830832834836838"
+  "840842844846848850852854856858860862864866868870872874876878"
+  "880882884886888890892894896898900902904906908910912914916918"
+  "920922924926928930932934936938940942944946948950952954956958"
+  "960962964966968970972974976978980982984986988990992994996998";
+
+// Table that maps i/2 to the length of i in characters.
+static char kIToALengthTable[500] = {
+  1, 1, 1, 1, 1,
+  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3};
+
+
+static char i_to_a_answer_buffer[12];
+
+
+// Calculate ASCII representation of a number 3 digits at a time.
+static char* RecursiveIToA(char* dest, int i) {
+  int low_triplet;
+  int thousands = 0;
+  while (true) {
+    low_triplet = (i & 1023);
+    int new_high_triplet = i >> 10;
+    low_triplet += new_high_triplet * 24;
+    thousands += new_high_triplet;
+    if (low_triplet < 1000) break;
+    if (low_triplet < 2000) {
+      low_triplet -= 1000;
+      thousands++;
+      break;
+    }
+    i = low_triplet;
+  }
+  if (thousands < 10) {
+    *dest++ = kIToATable[thousands * kIToATableStride + 1];
+  } else if (thousands < 100) {
+    dest[0] = kIToATable[thousands * kIToATableStride + 1];
+    dest[1] = kIToATable[thousands * kIToATableStride + 2];
+    dest += 2;
+  } else if (thousands < 1000) {
+    dest[0] = kIToATable[thousands * kIToATableStride + 1];
+    dest[1] = kIToATable[thousands * kIToATableStride + 2];
+    dest[2] = kIToATable[thousands * kIToATableStride + 3];
+    dest += 3;
+  } else {
+    dest = RecursiveIToA(dest, thousands);
+  }
+  const char* ascii_triplet = kLeadingZerosIToATable +
+                              (low_triplet >> 1) * kLeadingZerosIToATableStride;
+  dest[0] = ascii_triplet[0];
+  dest[1] = ascii_triplet[1];
+  dest[2] = (ascii_triplet[2] | (low_triplet & 1));
+  return dest + 3;
+}
+
+
+// Takes a 32 bit integer and returns a pointer to an ASCII representation of
+// that integer.  The caller need not free the returned representation.  The
+// ASCII representation is not necessarily null terminated, but the length is
+// written back to the 'len' argument.
+const char* IntToCString(int i, int* len) {
+  char* answer = i_to_a_answer_buffer;
+  if (i >= 0) {
+    if (i < 1000) {
+      // Handle 0-1000 by just returning a pointer to the table.
+      *len = kIToALengthTable[i >> 1];
+      return kIToATable + i * kIToATableStride + 1;
+    }
+    answer = RecursiveIToA(answer, i);
+    *len = answer - i_to_a_answer_buffer;
+    return i_to_a_answer_buffer;
+  } else {
+    // Negative numbers.
+    // Handle specially since there is no 32 bit positive representation of
+    // this number.  The C compiler seems to get very confused about it so
+    // we cast to unsigned to avoid warnings.
+    if (static_cast<unsigned>(i) == 2147483648u) {
+      *len = 11;
+      return "-2147483648";
+    }
+    i = -i;
+    if (i < 1000) {
+      if (i < 1000) {
+        *len = kIToALengthTable[i >> 1] + 1;
+        return kIToATable + i * kIToATableStride;
+      }
+    }
+    *answer++ = '-';
+    answer = RecursiveIToA(answer, i);
+    *len = answer - i_to_a_answer_buffer;
+    return i_to_a_answer_buffer;
+  }
+}
+
+
+
 const char* IntToCString(int n, Vector<char> buffer) {
   bool negative = false;
   if (n < 0) {